クヌースモリスプラットアルゴリズムの実装

Question

私はKMPアルゴリズムを実装しようとしています。 "if（W [i] == S [m + i]）"がインデックスから範囲外の例外を返すので、動作させることができません。

私はウィキペディア上の例を以下ました：M +私< S.Lengthが、それはWであるかもしれないときhttps://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

static int[] KMPTable(string W) 
    { 
     int[] T = new int[W.Length]; 
     int pos = 2; 
     int cnd = 0; 

     T[0] = -1; 
     T[1] = 0; 

     while (pos < W.Length) 
     { 
      if (W[pos - 1] == W[cnd]) 
      { 
       T[pos] = cnd + 1; 
       cnd = cnd + 1; 
       pos = pos + 1; 
      } 
      else 
       if (cnd > 0) 
       { 
        cnd = T[cnd]; 
       } 
       else 
       { 
        T[pos] = 0; 
        pos = pos + 1; 
       } 
     } 

     return T; 
    } 

    static int[] KMPSearch(string S, string W) 
    { 
     int m = 0; 
     int i = 0; 
     int[] kmpNext = KMPTable(S); 
     List<int> result = new List<int>(); 

     while (m + i < S.Length) 
     { 
      if (W[i] == S[m + i]) 
      { 
       if (i == W.Length - 1) 
       { 
        result.Add(m); 
       } 
        i = i + 1; 
      } 
      else 
      { 
       m = m + i - kmpNext[i]; 
       if (kmpNext[i] > -1) 
        i = kmpNext[i]; 
       else 
        i = 0; 
      } 
     } 
     return result.ToArray(); 
    } 

Answer 1

[i]はそのインデックスの外です。ステップバイステップのデバッグで確認してみてください。