时间戳

首页 > 解决方案 > 使用 Knuth Morris 计算每个前缀的出现次数

knuth-morris-pratt - 使用 Knuth Morris 计算每个前缀的出现次数

问题描述

我正在研究我的竞争性编码技能，我遇到了一篇文章，用于计算字符串中每个前缀的出现次数。这是问题陈述给定一个长度为 n 的字符串 s。在问题的第一个变体中，我们要计算每个前缀 s[0…i] 在同一字符串中出现的次数。在问题的第二个变体中，给出了另一个字符串 t，我们想要计算每个前缀 s[0…i] 在 t 中出现的次数。我找到了解决方案。

代码：

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]++;

据我所知前缀是什么，我无法完全理解问题陈述：

例如： string: geekforgeek 前缀为：{g,ge,gee,geek,geekf,geekfo,geekfor,geekforg,geekforge,geekforgee} 作为正确的前缀。有人可以帮我这个问题试图计算什么，因为只有这些是出现一次的可用前缀。提前致谢。

标签： knuth-morris-pratt

解决方案

如果你到目前为止我假设你知道prefix_function。所以我们考虑 string str = "ABACABA" 我们得到它的前缀数组 say pi as = {0, 0, 1, 0, 1, 2, 3} 来存储所有正确前缀的出现（即我们不包括字符串本身) 我们创建一个长度为 str.length()+1 的新数组或向量（根据您的需要）'occ'，其中 occ[i] 表示前缀 str[0:i] 的出现次数。

所以当你引用上面的代码时，有三个循环。首先，我必须解释这些循环实际上在计算什么。第一个循环很简单，它只计算最长前缀的编号，它也是长度为 i 的字符串中的后缀。对于前缀“A”，我们与 str[0:3] 和 str[0:5] 的前缀具有相同的后缀，如果仔细观察，可以说“A”是最长的前缀，也是这两个字符串的后缀，因此，我们从上面计算的数组 pi 中得到这个，因为它存储了最长前缀的长度，它也是一个后缀。同样，对于前缀“AB”，我们将其作为最长的前缀和后缀在 str[1:6] 中，依此类推。我们得到 occ = {3, 2, 1, 1, 0, 0, 0, 0}。我希望第一个循环的想法很清楚。

现在，当我们考虑上面前缀“A”的示例时，如果我们观察“ABACABA”，我们会看到在字符串 str[0:7] 中我们也有“A”作为后缀，但不是最长的前缀最长的地方== 后缀是“ABA”，所以在我们的第一个循环中，我们错过了前缀的出现。还假设如果我们有长度为 l 的前缀，它也是一个后缀并以索引 i 结束，并且为了得到一些长度为 l' < l 的前缀，我们选择 pi[pi[i]-1] 或说 pi[l-1 ] 从前缀函数中可以清楚地看出。因此，使用数组 pi 的这种方式，我们跟踪在第一个循环中计算的长度小于的前缀。如果我们知道长度前缀 i 恰好出现 occ[i] 次，那么这个数字必须添加到它的最长后缀（也是前缀）的出现次数上。

第三个循环是我们添加每个前缀的出现。而在其他两个中，我们只考虑后缀。

推荐阅读