使用Knuth Morris计算每个前缀出现的次数
我正在努力提高我的竞争性编码技巧--我偶然看到一篇文章，用来计算字符串中每个前缀出现的次数。下面是给定长度为n的字符串的问题陈述。在问题的第一个变体中，我们要计算每个前缀s0…的出现数。我用的是同一根绳子。在问题的第二个变体中，给出了另一个字符串t，我们希望计算每个前缀s0…的出现数。我找到了解决办法。
代码：
for (int i = 0; i < n; i++)
ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
ans[i]++;就我所知的前缀是什么，我无法完全理解问题陈述：
例如，
：geekfor前缀为：{g，ge，gee，geek，geekf，geekfo，geekfor，geekforg，geekforg，geekforg}作为适当的前缀。有人能帮我计算这个问题吗?因为只有这些前缀出现一次。提前谢谢。
。
回答 2
Stack Overflow用户
发布于 2020-07-17 08:48:21
如果你已经到达目前为止，我假设你知道prefix_function。因此，我们考虑字符串str = "ABACABA“，我们得到它的前缀数组，例如pi = {0，0，1，0，1，2，3}来存储所有正确前缀的出现(即我们不包括字符串本身)，我们创建了一个新的数组或向量(Acc)。长度为str.length()+1的“occ”，其中occi表示前缀str0:i出现的计数。
因此，正如您引用上面的代码一样，有三个循环。首先，我必须解释一下这些循环实际上是在计算什么。第一个循环很简单，它只计算长度为i的字符串中的最长前缀的no。对于前缀"A“，我们有与前缀str0:3和str0:5相同的后缀，如果注意到的话，可以说"A”是这两个字符串中也是后缀的最长前缀，因此我们从上面计算的数组pi中得到这一点，因为它存储了最长前缀的长度(也是后缀)。类似地，对于前缀"AB“，我们在str1:6中使用它作为最长前缀和后缀，以此类推。得到occ = {3，2，1，1，0，0，0，0}。我希望第一个循环的想法是明确的。
现在，当我们考虑前缀"A“的例子时，如果我们观察到"ABACABA"，我们看到在字符串str0:7中，我们也有"A”作为后缀，但是最长的前缀==后缀不是最长的，所以在我们的第一个循环中，我们忽略了这个前缀的出现。另外，假设我们有长度l的前缀，它也是一个后缀，在索引i处结束，为了得到长度l‘
对于第三个循环，我们添加每个前缀的出现。在另外两种情况下，我们只考虑后缀。
Stack Overflow用户
发布于 2022-11-14 09:35:02
代码应该是
{ for (int i = 0; i < n; i++)
ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
ans[pi[i]-1] += ans[i]; ///note the index
for (int i = 0; i <= n; i++)
ans[i]++;
}这篇文章是https://cp-algorithms.web.app/string/prefix-function.html#counting-the-number-of-occurrences-of-each-prefix，错误地提到了这个指数。如果我错了，请纠正我。
https://stackoverflow.com/questions/61916677
复制相似问题
腾讯云开发者
