关于kmp的许多文章提到，kmp中的failure函数本身有大量的应用程序。
其中一个应用程序是查找最小的字符串，当连接k次时，该字符串将给出原始字符串（句点）。
但我找不到其他的。还有哪些问题涉及kmp故障功能？
最佳答案
kmp计算字符串所有前缀的边界，这些前缀本身就是字符串算法中的一个关键概念。（计算整个单词本身的边界是非常重要的，而kmp（failure function）是这样做的标准！）
s的边界就是s的前缀和后缀。
正如您正确地注意到的，计算边界的能力的一个杰出应用是计算最小字符串w的可能性，这样对于给定字符串s的某些自然k w^k=s，这称为s的基元根。
其原因是字符串的边界和句点之间的二元性。字符串s的句点是任何长度不超过s的字符串，因此s是字符串w w w的前缀…例如，abc是abcabcab的一个周期。结果发现，单词的边框和句点之间存在1:1的对应关系；在上面的示例中，请注意abcab是abcabcab的边框。一般来说，只要w是s的句点，那么从s开始删除w后保留的字符串（w^-1s）就是s的边框。同样，如果w是s的边框，那么从s删除后缀w时保留的单词就是s的句点。
句点是分析字符串属性的重要工具。例如，它们用于查找字符串中的重复（运行）的算法；有关概述，请参见this paper.