关于KMP失效函数属性的说明

Question

我正在阅读 topcoder tutorial on KMP algorithm 但我无法理解文本的以下部分：

Given a string (a quite long one), find all its proper suffixes that are also prefixes of it. All we have to do is just to calculate the "failure function" of the given string and using the information stored in it to print the answer.

我知道如何计算失败函数，对于字符串 abacababa 我得到以下数组 [0, 0, 1, 0, 1, 2, 3, 2, 3]。问题是我不知道它如何帮助我找到

all its proper suffixes that are also prefixes of it

根据我的理解应该是 a 和 aba。

Answer 1

同时也是前缀的最长专有后缀是长度为 p[n - 1] 的前缀。下一个是这个后缀的最长后缀，也是一个前缀。恰好是一个长度为p[p[n - 1] - 1]的前缀。我们一直重复它，直到我们得到一个空前缀。

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

也是前缀的最长专有后缀是aba（因为p[n - 1]是3）。
也是aba前缀的最长专有后缀是a（因为p[2]是1）。
没有a(p[0] = 0)这样的后缀，所以我们完成了。

代码如下所示：

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

关于KMP失效函数属性的说明

Explanation about the property of KMP failure function

algorithm

knuth-morris-pratt