string - 有效地计算可被k整除的数字字符串的子字符串的数量？

Question

我们给了一个由数字0-9组成的字符串。我们必须计算可被数字k整除的子字符串的数量。一种方法是生成所有子字符串，并检查它是否可以被k整除，但这将花费O(n^2)时间。我想在O(n*k)时间内解决此问题。

1 <= n <= 100000 and 2 <= k <= 1000.

我看到了类似的问题here。但是，在该问题中，k固定为4。因此，我使用了除数为4的属性来解决该问题。
这是我对这个问题的解决方案:

int main()
{
    string s;
    vector<int> v[5];
    int i;
    int x;
    long long int cnt = 0;

    cin>>s;
    x = 0;
    for(i = 0; i < s.size(); i++) {
        if((s[i]-'0') % 4 == 0) {
            cnt++;
        }
    }
    for(i = 1; i < s.size(); i++) {
        int f = s[i-1]-'0';
        int s1 = s[i] - '0';
        if((10*f+s1)%4 == 0) {
            cnt = cnt + (long long)(i);
        }
    }
    cout<<cnt;

}

但是我想要一个适用于k值的通用算法。

Answer 1

这是一个非常有趣的问题。与其跳入最终的整体算法，不如说我会从一个合理的算法开始，然后再对其进行一系列修改，以最终的O(nk)时间算法结束。

这种方法将许多不同的技术结合在一起。主要技术是在数字上计算滚动余数的想法。例如，假设我们要查找字符串的所有前缀，这些前缀是k的倍数。我们可以通过列出所有前缀并检查每个前缀是否为k的倍数来做到这一点，但是由于存在Θ(n2)个不同的前缀，因此至少要花费Θ(n2)。但是，我们可以通过变得更聪明在时间Θ(n)中执行此操作。假设我们知道已经读取了字符串的前h个字符，并且知道了以这种方式形成的数字的其余部分。我们也可以使用它来说明字符串的前h + 1个字符的其余部分，因为通过附加该数字，我们得到的是现有数字，将其乘以10，然后加上下一个数字。这意味着如果我们有r的余数，那么我们的新余数是(10r + d)mod k，其中d是我们发现的数字。

这是快速的伪代码，用于计算字符串的前缀数，该前缀数是k的倍数。它在时间Θ(n)中运行:

remainder = 0
numMultiples = 0
for i = 1 to n: // n is the length of the string
    remainder = (10 * remainder + str[i]) % k
    if remainder == 0
        numMultiples++
return numMultiples

我们将使用这种初始方法作为整体算法的构建块。

因此，现在我们有了一种算法，可以找到字符串的前缀数，该前缀数是k的倍数。我们如何将其转换为找到k的倍数的子字符串数量的算法？让我们从一种不太可行的方法开始。如果我们计算原始字符串的所有前缀，这些前缀是k的倍数，然后删除字符串的第一个字符并计算剩余的前缀，然后删除第二个字符并计算剩余的前缀，等等？最终将找到每个子字符串，因为原始字符串的每个子字符串都是该字符串的某些后缀的前缀。

这是一些粗略的伪代码:

numMultiples = 0
for i = 1 to n:
    remainder = 0
    for j = i to n:
        remainder = (10 * remainder + str[j]) % k
        if remainder == 0
            numMultiples++
return numMultiples

例如，在字符串14917上运行此方法以查找7的倍数将打开以下字符串:

字符串14917:查找14，1491，14917

字符串4917:查找49，

字符串917:查找91，917

字符串17:什么都找不到

字符串7:查找7

关于此方法的好消息是它将找到所有有效的子字符串。坏消息是它在时间Θ(n2)中运行。

但是，让我们看一下在此示例中看到的字符串。例如，查看通过搜索整个字符串的前缀找到的子字符串。我们找到了其中三个:14，1491和14917。现在，看一下这些字符串之间的“差异”:

14和14917之间的区别是917。

14和1491之间的区别是91

1491和14917之间的区别是7。

请注意，每个字符串的区别本身就是14917的子字符串，它是7的倍数，实际上，如果您查看稍后在算法运行中匹配的其他字符串，我们会发现其他字符串也一样

这不是巧合。如果您有两个具有相同前缀的数字，它们是相同数字k的倍数，则它们之间的“差”也将是k的倍数。 (检查一下数学是一个很好的练习。)

因此，这表明我们可以采取另一条路线。假设我们发现原始字符串的所有前缀都是k的倍数。如果可以找到所有这些前缀，则可以找出这些前缀之间有多少成对的差异，并有可能避免多次重新扫描。这不一定会找到所有内容，但是它将找到可以通过计算两个前缀的差值形成的所有子字符串。在所有后缀上重复此操作-并注意不要重复计算-确实可以加快处理速度。

首先，假设我们找到了r个不同的字符串前缀，它们是k的倍数。如果我们包含差异，我们只发现了多少个子字符串？好吧，我们发现了k个字符串，并且为每对(无序)元素对添加了一个额外的字符串，得出的总k + k(k-1)/2 = k(k + 1)/2个子字符串。不过，我们仍然需要确保我们不会重复计算。

要查看我们是否重复计算某物，可以使用以下技术。在计算沿字符串的滚动余数时，我们将存储在每次输入后找到的余数。如果在计算滚动余数的过程中，我们重新发现某个时候已经计算出的余数，那么我们知道我们正在做的工作是多余的。之前对该字符串进行的一些扫描将已经计算出了余数，并且从现在开始我们发现的任何内容都将被找到。

将这些想法放在一起可以得到以下伪代码:

numMultiples = 0
seenRemainders = array of n sets, all initially empty
for i = 1 to n:
    remainder = 0
    prefixesFound = 0
    for j = i to n:
        remainder = (10 * remainder + str[j]) % k
        if seenRemainders[j] contains remainder:
            break
        add remainder to seenRemainders[j]
        if remainder == 0
            prefixesFound++
    numMultiples += prefixesFound * (prefixesFound + 1) / 2
return numMultiples

那么，这有多有效？乍一看，由于外部循环，它看起来像在时间O(n2)上运行，但这并不是一个严格的界限。请注意，每个元素最多只能在内部循环中传递k次，因为在此之后，没有任何余数仍然是空闲的。因此，由于每个元素最多被访问O(k)次，并且总共有n个元素，因此运行时为O(nk)，这满足您的运行时要求。