KMP的失败函数

Question

我最近学会了KMP字符串匹配算法，并且我差不多全部都完成了。但我没有得到的是如何在O中构建失败函数（ length_of_pattern）。我不要需要代码，如果可能的话，我需要一个明确的解释。提前致谢！

Answer 1

从this site：

的KMP算法预处理图案P通过计算故障函数f表示的最大可能的偏移s使用先前执行的比较。

具体而言，故障函数f（j）被定义为作为P [i的后缀的P的最长前缀的长度。 。 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 

希望这回答你的问题