string - KMP失效函数的应用

Question

很多关于 KMP 的文章都提到了 KMP 本身的故障函数有大量的应用。

一个这样的应用程序是找到最小的字符串，当连接 k 次时给出原始字符串（句点）。

但我找不到其他的。还有哪些问题涉及 KMP 失效功能？

Answer 1

KMP 计算字符串的所有前缀的边界，它们本身就是字符串算法中的一个关键概念。（计算整个单词的边界本身并不简单，KMP（失效函数）就是这样做的标准！）

s的边框就是任何既是s的前缀又是后缀的单词。

正如您正确注意到的，计算边界能力的一个突出应用是计算最小字符串 w 的可能性，使得对于给定字符串s的某些自然 k w ^k = s。这称为 s 的原根。

其原因是字符串的边界和句点之间的对偶性。字符串s的句点是任何不长于s 的字符串w，因此s是字符串 wwww 的前缀……例如，abc是abcabcab的句点。事实证明，单词的边界和句点之间存在 1:1 的对应关系；在上面的示例中，请注意abcab是 abcabcab 的边框。一般来说，只要w是s 的一个周期，那么在移除w之后从s中剩下的字符串从一开始（w ^-1 s）就是 s 的边界。类似地，如果w是s的边界，那么当您删除后缀w时，从s中剩余的单词就是s的句点。

句点是分析字符串属性的重要工具。例如，它们用于在字符串中查找重复（运行）的算法中；有关概述，请参阅本文。