Найдите подпоследовательности строки, длина которой достигает 10 000

У меня есть строка, размер которой может достигать «10 000». Я должен посчитать те ПОДПОСЛЕДОВАТЕЛЬНОСТИ, которые делятся на 9.

ПОДПОСЛЕДОВАТЕЛЬНОСТЬ :Подпоследовательность — это расположение, в котором поддерживается порядок символов данной строки. Например, :если данная строка равна 10292, то некоторые из ее подпоследовательностей равны 1, 102, 10, 19, 12, 12 (12 вдвое больше, чем 2, встречается дважды ), 129, 029, 09, 092 и т. д..Некоторые числа, которые не являются подпоследовательностями данной строки, это :201 (2 и 0 не может стоять перед 1 ), 921, 0291 и т. д.

Я попытался сгенерировать все подпоследовательности (powerset )заданной строки, используя сдвиг битов и проверяя каждую строку, если она делится на 9. Но это работает нормально, пока длина строки <= 10. После этого я не получаю правильных подпоследовательностей (некоторые подпоследовательности отображаются отрицательными числами ).

Ниже мой код:

    scanf("%s", &str); //input string 

    int n=strlen(str); //find length of string

    //loop to generate subsequences
    for(i=1;i<(1<<n);++i){

        string subseq;

        for(j=0;j<n;++j){

            if(i&(1<<j)){

                subseq+=str[j]; // generate subsequence
            }
        }

        //convert generated subseq to int; number is 'long' tpye
        number=atol(subseq.c_str());printf("%ld\n", number); 

        //ignore 0 and check if number divisible by 9
        if(number!=0&&number%9==0)count++;
    }

        printf("%ld\n", count);