KMPアルゴリズムが複数回バックトラックする必要がある場合の例を構築する

Question

特定のi（LPS配列のセル）に対してkmp algorithmcomputeLPSArrayフェーズを何度もバックトラック（以下のコメントを参照）する必要がある例を構築しようとしています。 。

'AAACAAA'のために、それはあなたが私はそれが特定のiのためにバックトラックセクション3-4回を訪問する文字列を構築助けることができる二回i = 3ため、一度i = 7

のためのバックトラックセクションを訪問しますか？ 'AAAACAA'で

def computeLPSArray(pat, M, lps): 
    len = 0 # length of the previous longest prefix suffix 
    lps[0]=0 # lps[0] is always 0 
    i = 1 
    while i < M: 
    if pat[i]==pat[len]: 
     len+=1 
     lps[i] = len 
     i+=1 
    else: 
     if len!=0: 
      # backtrack section - When will we get here 3-4 times for the same i??? 
      len = lps[len-1]  
     else: 
      lps[i] = 0 
      i+=1 

Answer 1

はそれがi = 4のためにバックトラックセクションを3回訪問します。

'AAAAACA'で、i = 5のバックトラックセクションを4回訪問します。

Answer 2

あなたがすでに言及したように、あなたの例の文字列AAACAAAは、i = 3のときにすでにバックトラックセクションを2回訪れました。

訪問数を増やしたい場合は、接頭辞のAの数を増やしてください（例：

AAAAC 

バックトラックセクションを3回訪れます。