Shi*_*tra 6 string algorithm big-o time-complexity
我们得到一个由数字组成的字符串0-9。我们必须计算可以被一个数整除的子串的数量k。一种方法是生成所有子字符串并检查它是否可以被 整除，k但这需要O(n^2)时间。我想及时解决这个问题O(n*k)。
1 <= n <= 100000 and 2 <= k <= 1000.
我在这里看到了一个类似的问题。但是在那个问题中，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 值的通用算法。
这是一个非常有趣的问题。我认为我应该从一个不太合理的算法开始，而不是跳到最终的整体算法，然后对其进行一系列修改，最终得到最终的 O(nk) 时间算法。
\n这种方法结合了多种不同的技术。主要技术是计算数字上的滚动余数的想法。例如，假设我们想要查找字符串中所有为 k 倍数的前缀。我们可以通过列出所有前缀并检查每个前缀是否是 k 的倍数来做到这一点，但这至少需要 \xce\x98(n 2 ) 时间，因为存在 \xce\x98(n 2 ) 不同的前缀。然而，我们可以通过更聪明一点来及时做到这一点。假设我们知道我们已经读取了字符串的前 h 个字符，并且我们知道以这种方式形成的数字的其余部分。我们也可以用它来表示字符串的前 h+1 个字符的其余部分，因为通过附加该数字，我们将获取现有数字，将其乘以 10，然后添加下一个数字。这意味着如果我们有 r 的余数，那么新的余数就是 (10r + d) mod k，其中 d 是我们发现的数字。
\n下面是计算字符串中 k 倍数前缀数量的快速伪代码。它在时间 \xce\x98(n) 中运行：
\nremainder = 0\nnumMultiples = 0\nfor i = 1 to n: // n is the length of the string\n remainder = (10 * remainder + str[i]) % k\n if remainder == 0\n numMultiples++\nreturn numMultiples\n我们将使用这个初始方法作为整个算法的构建块。
\n现在我们有一个算法可以找到字符串中 k 倍数的前缀数量。我们如何将其转换为查找k 倍数子串数量的算法？让我们从一种不太有效的方法开始。如果我们计算原始字符串中所有 k 倍数的前缀，然后去掉字符串的第一个字符并计算剩下的前缀，然后去掉第二个字符并计算剩下的前缀，等等，会怎么样？这最终将找到每个子字符串，因为原始字符串的每个子字符串都是该字符串的某些后缀的前缀。
\n这是一些粗略的伪代码：
\nnumMultiples = 0\nfor i = 1 to n:\n remainder = 0\n for j = i to n:\n remainder = (10 * remainder + str[j]) % k\n if remainder == 0\n numMultiples++\nreturn numMultiples\n例如，在字符串上运行此方法来14917查找 的倍数7将出现以下字符串：
14917：查找14, 1491,14917 4917：查找49， 917：查找91，917 17：什么也没找到 7：找到7这种方法的好消息是它会找到所有有效的子字符串。坏消息是它运行时间为 \xce\x98(n 2 )。
\n但让我们看一下在此示例中看到的字符串。例如，查看通过搜索整个字符串的前缀找到的子字符串。我们找到了其中三个：14、1491和14917。现在，看看这些字符串之间的“差异”：
14和之间的区别14917是917。14和之间的区别1491是911491和之间的区别14917是7。请注意，每个字符串的差异本身就是149177 的倍数的子字符串，事实上，如果您查看我们稍后在算法运行中匹配的其他字符串，我们会发现这些其他字符串为出色地。
这并非巧合。如果有两个具有共同前缀的数字，并且它们是同一数字 k 的倍数，那么它们之间的“差”也将是 k 的倍数。（这是一个很好的练习来检查这方面的数学。）
\n所以这表明我们可以采取另一条路线。假设我们找到原始字符串中所有为 k 倍数的前缀。如果我们能找到所有这些，我们就可以计算出这些前缀之间有多少成对差异，并可能避免多次重新扫描。这不一定会找到所有内容，但它会找到通过计算两个前缀之差可以形成的所有子字符串。对所有后缀重复此操作 - 并小心不要重复计算 - 确实可以加快速度。
\n首先，假设我们找到了 r 个不同的字符串前缀，它们是 k 的倍数。如果包含差异，我们总共找到了多少个子串？好吧，我们找到了 k 个字符串，再加上每对（无序）元素一个额外的字符串，总共发现了 r + r(r-1)/2 = r(r+1)/2 个子字符串。不过，我们仍然需要确保不会重复计算。
\n要查看是否重复计算某些内容，我们可以使用以下技术。当我们计算沿字符串的滚动余数时，我们将存储在每个条目之后找到的余数。如果在计算滚动余数的过程中，我们重新发现了我们在某个时刻已经计算过的余数，我们就知道我们正在做的工作是多余的；之前对字符串的一些扫描将已经计算出这个余数，并且我们从此时开始发现的任何内容都将已经找到。
\n将这些想法放在一起，我们得到了这个伪代码：
\nnumMultiples = 0\nseenRemainders = array of n sets, all initially empty\nfor i = 1 to n:\n remainder = 0\n prefixesFound = 0\n for j = i to n:\n remainder = (10 * remainder + str[j]) % k\n if seenRemainders[j] contains remainder:\n break\n add remainder to seenRemainders[j]\n if remainder == 0\n prefixesFound++\n numMultiples += prefixesFound * (prefixesFound + 1) / 2\nreturn numMultiples\n那么这有多有效呢？乍一看，由于存在外部循环，这看起来运行时间为 O(n 2 )，但这并不是一个严格的界限。请注意，每个元素最多只能在内部循环中传递 k 次，因为之后就没有任何剩余元素仍然可用。因此，由于每个元素最多被访问 O(k) 次，并且总共有 n 个元素，因此运行时间为 O(nk)，这满足了您的运行时间要求。
\n| 归档时间： |
|
| 查看次数： |
3018 次 |
| 最近记录： |