string - KMP失效函数的应用

Question

很多关于KMP的文章都提到KMP中的failure函数本身就有大量的应用。

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

但我找不到其他的。 KMP失效函数还有哪些问题？

Answer 1

KMP 计算字符串所有前缀的边界，这本身就是字符串算法中的一个关键概念。 (计算整个单词的边界本身并不简单，KMP(失效函数)是执行此操作的标准!)

s 的边界只是任何既是s 的前缀又是后缀的单词。

正如您正确注意到的那样，计算边界能力的一个突出应用是计算最小字符串 w 的可能性，使得对于某些自然 k w^k = s 对于给定的字符串 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 的句点。

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