KMPの失敗関数

Question

最近、私はKMP文字列マッチングアルゴリズムを学びました。しかし私が得られないのは、O（ length_of_pattern）で失敗機能を構築する方法です。私はコードを必要としない、私は可能な場合は明確な説明が必要です。前もって感謝します！ this siteから

Answer 1

：

可能な最大シフトの使用以前に実行される比較を示す故障関数fを計算することによって、パターンPプリプロセスKMPアルゴリズム。

特に、障害関数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 

が、それはあなたの質問