Knuth Morris Pratt算法实现

我试图实现KMP算法。部分“if（W [i] == S [m + i]）”将索引超出范围异常并且我无法使其工作。Knuth Morris Pratt算法实现

我被下列维基百科例如：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(); 
    }

来源

2017-04-01 metalcamp

我建议你在if语句之前检查值。这会让你知道W.length，S.length，i和m的值是什么。您将能够看到发生了什么以及需要更改算法的位置。 – Mark

当M + 1 < S.Length，那么它可能是W [I]即出其索引。尝试检查一步一步的调试。

来源

2017-04-01 17:55:32 oelsardine

Knuth Morris Pratt算法实现

回答

相关问题