KMP失效函数的应用

Question

许多关于KMP的文章都提到，KMP中的故障函数本身就有大量的应用。

一个这样的应用是寻找最小的字符串，当连接k次时，它给出了原始字符串(句点)。

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

Answer 1

KMP计算字符串所有前缀的边界，这本身就是字符串算法中的一个关键概念。(计算整个单词本身的边界是很重要的，KMP (失败函数)就是这样做的标准！)

s的边框就是同时是s的前缀和后缀的任何单词。

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

这是因为字符串的边框和句点之间的二元性。字符串s的前缀period是任何不长于s的字符串w，使得s是字符串wwww…的前缀。例如，abc是abc的句号。事实证明，一个单词的边框和句点之间存在1:1的对应关系；在上面的示例中，请注意abcab是abcab的边框。一般来说，只要w是s的句号，那么从s开始删除w (w^-1 s)后剩余的字符串就是s的边框。类似地，如果w是s的边框，那么删除后缀w时s剩下的单词就是s的句号。

句点是分析字符串属性的重要工具。例如，它们用于查找字符串中的重复项(运行)的算法中；有关概述，请参阅this paper.