string - KMP的故障功能

我最近学习了kmp字符串匹配算法，我几乎得到了所有的知识。但我没有得到的是如何在o（模式的长度）中建立失效函数。我不需要代码，我需要一个明确的解释，如果可能的话提前谢谢！

最佳答案

从this site：
kmp算法通过计算故障函数f来预处理模式p，该故障函数f使用先前执行的比较来指示最大可能的移位s。
具体地说，失效函数f（j）被定义为P的最长前缀的长度，该前缀是P[i]的后缀.j]。
这是构造的伪代码，我想你可以在网站上得到解释的细节

        KNUTH-MORRIS-PRATT FAILURE (P)

            Input:    Pattern with m characters
            Output: Failure function f for P[i . . j]

            i ← 1
            j ← 0
            f(0) ← 0
            while i < m do    /// your complexity will be O(length of pattern)
                if P[j] = P[i]
                    f(i) ← j +1
                     i ← i +1
                      j← j + 1
                else if (j != 0)
                     j ← f(j - 1)
                else
                    f(i) ← 0
                    i ← i +1

希望它能回答你的问题

关于string - KMP的故障功能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6594072/