KMP計算プレフィックス関数の結果を表示

Question

私は学校の宿題を解決しようとしています、それはKMPアルゴリズムに関係しています。ここで私の計算プレフィックス関数ですが、プレフィックステーブルを出力すると仮定していますが、すべてが0を返すたびに実行されます。私は何が間違っているのか理解するのに役立つでしょうか？ありがとう！

static int[] computePrefixFunction(string P) 
     { 
      int m = P.Length; 
      int[] pi = new int[m]; 
      pi[1] = 0; 
      int k = 0; 

      for (int j = 2; j < m; j++) 
      { 
       while (k > 0 && P[k + 1] != P[j]) 
       { 
        k = pi[k]; 
       } 
       if (P[k+1] == P[j]) 
       { k = k + 1; }; 
       pi[j] = k; 
      } 

      for (int i = 0; i < pi.Length; i++) 
      { 
       Console.WriteLine(pi[i]); 
      } 
      return pi; 
     } 

Answer 1

あなたはインデックスのオフセットを混乱させました。ここでは固定されたバージョンは次のとおりです。

static int[] computePrefixFunction(string P) 
{ 
    int m = P.Length; 
    int[] pi = new int[m]; 
    int k = 0; 

    for (int j = 1; j < m; j++) 
    { 
     k = pi[j - 1]; 

     while (k > 0 && P[k] != P[j]) 
      k = pi[k-1]; 

     if (P[k] == P[j]) 
      k = k + 1; 

     pi[j] = k; 
    } 

    return pi; 
} 

ライブデモ：https://dotnetfiddle.net/YQknMp