algorithm - KMP失效函数性质说明

Question

我正在阅读关于 KMP 算法的 topcoder 教程，但我无法理解文本的以下部分：

给定一个字符串（一个很长的字符串），找到它的所有正确的后缀，这些后缀也是它的前缀。我们所要做的只是计算给定字符串的“失败函数”，并使用其中存储的信息来打印答案。

我知道如何计算故障函数，对于字符串abacababa，我得到以下数组[0, 0, 1, 0, 1, 2, 3, 2, 3]。问题是我无法弄清楚它如何帮助我找到

它的所有正确的后缀也是它的前缀

根据我的理解假设是aand aba。

Answer 1

也是前缀的最长的正确后缀是 length 的前缀p[n - 1]。下一个是这个后缀中最长的后缀，也是一个前缀。它恰好是 length 的前缀p[p[n - 1] - 1]。我们不断重复它，直到我们得到一个空前缀。

例如，对于该abacaba字符串，它是这样的：

1. 最长的正确后缀也是前缀是aba（因为p[n - 1]is 3）。

2. 最长的专有后缀，也是 is 的前缀aba（a因为p[2]is 1）。

3. a( )没有这样的后缀p[0] = 0，所以我们完成了。

代码如下所示：

cur = p[n - 1]
while cur != 0:
     print(s[0 ... cur - 1])
     cur = p[cur - 1]