关于KMP的许多文章都提到KMP本身的故障功能有很多应用.
一个这样的应用是找到最小的字符串,当连接k次时给出原始字符串(句点).
但我找不到任何其他的东西.还有哪些其他问题涉及KMP故障功能？
KMP 计算字符串所有前缀的边界，这本身就是字符串算法中的关键概念。（计算整个单词的边界本身就很重要，KMP（失败函数）是这样做的标准！）
s的边界就是既是s的前缀又是后缀的任何单词。
正如您正确地注意到的，计算边界能力的一个突出应用是计算最小字符串 w 的可能性，使得对于给定字符串s的某些自然 k w ^k = s。这称为s 的原根。
其原因是字符串的边界和句点之间的二元性。字符串s的句点是不长于s的任何字符串w，使得s是字符串wwww的前缀...例如，abc是abcabcab的句点。事实证明，单词的边界和句点之间存在 1:1 的对应关系；在上面的示例中，请注意abcab是abcabcab的边框。一般来说，只要w是s的一个周期，那么从s的开头删除w后剩下的字符串( w ^-1 s ) 就是s的边界。类似地，如果w是s的边界，那么当您删除后缀w时，从s中保留的单词就是s的句点。
句点是分析字符串属性的重要工具。例如，它们用于查找字符串中重复（运行）的算法；有关概述，请参阅本文。