FシャープKMPアルゴリズムは、最初の2つのインデクスで同じ文字のパターンを使用すると、最初のwhileループでスタックされます

Question

私はKシャープでKMPアルゴリズムを使いこなしています。 "ATAT"（結果は[| 0; 0; 1; 2; |]）のようなパターンで動作しますが、最初のwhileループは文字列の最初の2文字が同じで、3文字目が別の場合例えば、 "AAT"とする。

私は理解しています：最初に、私は1に増えます。今度は "A" <> "T"のため、whileループの最初の条件は真です。今度は私に接頭辞テーブル[！i]を設定します。これはもう一度1で、ここに行きます。

あなたは私にこれを解決するためのヒントを教えてもらえますか？

let kMPrefix (pattern : string) = 

    let (m : int) = pattern.Length - 1 
    let prefixTable = Array.create pattern.Length 0 
    // i : longest proper prefix that is also a suffix 
    let i = ref 0 

    // j: the index of the pattern for which the prefix value will be calculated 
    // starts with 1 because the first prefix value is always 0 

    for j in 1 .. m do 

     while !i > 0 && pattern.[!i] <> pattern.[j] do 

      i := prefixTable.[!i] 

     if pattern.[!i] = pattern.[j] then 

      i := !i+1   


     Array.set prefixTable j !i 

    prefixTable 

Answer 1

私はそれが（少なくとも私は、Wikipediaで見つけたもの）、であるKMPアルゴリズムのルックアップテーブルの内容と一致していないので、小さな変更でコードを修復するかどうかはわかりません。 0

そうでない場合は、インデックスのための

• -1、最初に一致する現在位置の前に連続する要素の数したがって

（初め自体を除く）、私は思います"ATAT"の出力は[|0; 0; 1; 2;|]ではなく[|-1; 0; 0; 1|]になると予想します。

この種の問題は、機能的なスタイルでは、このような問題が発生する可能性があります。 KMPテーブルを作成するには、テーブルを1つずつ書き込む再帰関数を使用し、最新の文字の数を最初の文字に一致させて追跡し、2番目の文字のインデックスでそれを実行することができます。

可能な実装：runのすべてのコードパスは、次の反復又は仕上げ反復でwriteIndexを高めるいずれかのため

let buildKmpPrefixTable (pattern : string) = 
    let prefixTable = Array.zeroCreate pattern.Length 

    let rec run startIndex matchCount = 
     let writeIndex = startIndex + matchCount 
     if writeIndex < pattern.Length then 
      if pattern.[writeIndex] = pattern.[matchCount] then 
       prefixTable.[writeIndex] <- matchCount 
       run startIndex (matchCount + 1) 
      else 
       prefixTable.[writeIndex] <- matchCount 
       run (writeIndex + 1) 0 
    run 1 0 
    if pattern.Length > 0 then prefixTable.[0] <- -1 
    prefixTable 

このアプローチは、任意の無限ループ/再帰の危険にさらされません。

注意：この問題で説明しているエラーは、無限ループまたはより一般的には非終端の繰り返しです。デッドロックとは、スレッドを保持しているスレッド自体が同じ理由で解放されないロックを待っているために、スレッドが決して解放されないロックを待つ状況を指します。