查找长度大到10,000的字符串的子序列

Question

我有一个字符串,其大小可以大到"10,000".我必须计算那些可以被9整除的后缀.

SUBSEQUENCE:子序列是一种保持给定字符串的字符顺序的安排.例如:如果给定的字符串是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);

Answer 1

由于一个数字可以被九整除当且仅当它的数字之和可以被九整除时，您可以使用递归算法来解决这个问题O(n)。

这个想法如下：在每一步，将子序列分成两部分，并（递归地）确定有多少个序列的数字之和为i % 9，其中i范围为0到8。O(1)然后，您可以通过以下方式“合并”两个表来为整个范围构建相同的表。假设是左分割和右分割L的表，您需要为整个范围构建表。RF

那么你有：

for (i = 0; i < 9; i++) {
  F[i] = L[i] + R[i];
  for (j = 0; j < 9; j++) {
    if (j <= i)
      F[i] += L[j] * R[i - j]
    else
      F[i] += L[j] * R[9 + i - j]
  }
}

仅一位数字的子序列的基本情况d很明显：只需将F[d % 9] = 1所有其他条目设置为零。

完整的 C++11 实现：

#include <iostream>
#include <array>
#include <tuple>
#include <string>

typedef std::array<unsigned int, 9> table;

using std::tuple;
using std::string;

table count(string::iterator beg, string::iterator end)
{
    table F;
    std::fill(F.begin(), F.end(), 0);
    if (beg == end)
        return F;
    if (beg + 1 == end) {
        F[(*beg - '0') % 9] = 1;
        return F;
    }
    size_t distance = std::distance(beg, end);
    string::iterator mid = beg + (distance / 2);
    table L = count(beg, mid);
    table R = count(mid, end);

    for (unsigned int i = 0; i < 9; i++) {
        F[i] = L[i] + R[i];
        for(unsigned int j = 0; j < 9; j++) {
            if (j <= i)
                F[i] += L[j] * R[i - j];
            else
                F[i] += L[j] * R[9 + i - j];
        }
    }
    return F;
}

table count(std::string s)
{
    return count(s.begin(), s.end());
}

int main(void)
{
    using std::cout;
    using std::endl;
    cout << count("1234")[0] << endl;
    cout << count("12349")[0] << endl;
    cout << count("9999")[0] << endl;
}