如何使用 KMP 失败函数来确定最小长度重复子串？

Question

我想使用 KMP 算法解决UVA 10298 -“电源字符串”问题。在这个博客中，展示了一种技术如何使用失败函数来计算最小长度重复子串。该技术如下：

计算pi[ ]给定字符串的前缀-后缀表。
让len成为字符串长度，并last_in_pi成为存储在pi表的最后一个索引处的值。
检查是否len % (len - last_in_pi) == 0属实。如果为真，则最小长度重复子串的长度为(len - last_in_pi)，否则为给定字符串的长度。

我了解什么是失败函数以及如何使用它在文本中查找模式，但我很难理解这种技术的正确性证明。

Answer 1

请记住，它Pi[i]被定义为最长前缀的（长度your_string）是 substring 的适当后缀（因此不是整个字符串）your_string[0 ... i]。

您链接到的博客文章中有一个示例：

    0 1 2 3 4 5
S : a b a b a b
Pi: 0 0 1 2 3 4

我们有：

一b一

ab ab

等等。我希望这能说明Pi（前缀函数/表）的作用。

现在，博客说：

前缀表的最后一个值 = 4.. 现在如果它是一个重复的字符串比，它的最小长度将是 2. (6(string length) – 4) , 现在

所以你必须检查是否len % (len - last_in_pi) == 0. 如果是，则len - last_in_pi是最短重复字符串（句点字符串）的长度。

这是有效的，因为如果您以len(period)任何一种方式旋转带有位置的字符串，它都会匹配自身。len - last_in_pi告诉您需要旋转多少。