JavaでのKMPアルゴリズムの実装方法は何ですか?

イラスト

kmp アルゴリズムは、前述の bm アルゴリズムの考え方と似ています。前述したように、bm アルゴリズムには良いサフィックスという概念があり、kmp には良いプレフィックスという概念があります。良いプレフィックスとは何ですか? まず、次の例を見てみましょう。

上記の例に注目してください。すでに一致している abcde は適切なプレフィックスと呼ばれ、a は次の bcde と一致しないため、再度比較する必要はありません。直後にスライドします。以上です。

適切なプレフィックスに一致する文字がある場合はどうなりますか?

上記の例に注目してください。この時点で適切なプレフィックスの直後にスライドすると、スライドしすぎて、一致する部分文字列を見逃してしまいます。では、適切なプレフィックスに基づいて適切なスライディングを実行するにはどうすればよいでしょうか?

実際には、現在の適切なプレフィックスのプレフィックスとサフィックスが一致するかどうかを確認し、一致する最長の長さを見つけて、直接スライドします。最長一致長を複数回見つけることを考慮して、最初に配列を初期化し、現在の適切なプレフィックスの下に最長一致長を保存すると、次の配列が出力されます。

現在の適切なプレフィックスの下にある適切なプレフィックスのプレフィックスとサフィックスの最も長く一致する部分文字列の長さを表す次の配列を定義します。この最長一致長は、この部分文字列が以前に一致したことを意味します。部分文字列の次の文字から直接照合を再度行う必要があります。

next[i] を計算するたびにすべての文字を照合する必要がありますか? 不必要な比較を減らすために next[i - 1] に基づいて推測できますか? 。

この考えに基づいて、次の手順を見てみましょう:

次[i - 1] = k - 1と仮定します;

If modelStr[k] = modelStr [ i] then next[i]=k

##modelStr[k] != modelStr[i] の場合、 next[i] = next[i - 1 を直接決定できますか? 】？

上記の例を通じて、next[i]!=next[i-1]、次にmodelStr[k]!=modelStr At [i]であることが明確にわかります。 、next[0]、next[1]...next[i-1]はすでにわかっていますが、next[i]をひっくり返すにはどうすればよいでしょうか？

modelStr[x…i] が、プレフィックスとサフィックスが一致する最長のサフィックス部分文字列であると仮定すると、最長一致するプレフィックス部分文字列は、modelStr[0…i-x]

# になります。 ##最長の一致する文字列が見つかった場合、その前の 2 番目に長い一致する文字列 (現在の i を除く)、つまり、modelStr[x…i-1] は以前に解決されているはずです。解決済みの特定の一致文字列を見つけます。プレフィックス部分文字列が modelStr[0…i-x-1]、サフィックス部分文字列がmodelStr[x…i-1]、およびmodelStr[i-x] == modelStr [i]であると仮定します。この接頭辞と接尾辞の部分文字列は 2 番目の接頭辞部分文字列であり、さらに現在の文字は一致する最長の接頭辞と接尾辞の部分文字列です。

コード実装

まず、kmp アルゴリズムで最も重要な次の配列です。この配列は、現在の添え字までの部分文字列に一致する最長のプレフィックスとサフィックスの数をマークします。アルゴリズム, if 特定の接頭辞が適切な接頭辞である場合、つまりパターン文字列接頭辞と一致する場合、特定のテクニックを使用して複数の文字を前方にスライドさせることができます。詳細については、前の説明を参照してください。どのプレフィックスが適切であるかは事前には分からず、照合プロセスは複数回行われるため、最初に初期化メソッドを呼び出して次の配列を初期化します。

1. 前の文字の最長プレフィックス部分文字列の次の文字 == 現在の文字の場合、前の文字の最長プレフィックス部分文字列を現在の文字に直接追加できます

2等しくない場合は、現在の部分文字列と等しい、既存の最長の接頭辞部分文字列の次の文字を見つけて、現在の文字部分文字列の最長の接頭辞接尾部部分文字列

int[] next ;
    /**
     * 初始化next数组
     * @param modelStr
     */
    public void init(char[] modelStr) {
        //首先计算next数组
        //遍历modelStr，遍历到的字符与之前字符组成一个串
        next = new int[modelStr.length];
        int start = 0;
        while (start < modelStr.length) {
            next[start] = this.recursion(start, modelStr);
            ++ start;
        }
    }

    /**
     *
     * @param i 当前遍历到的字符
     * @return
     */
    private int recursion(int i, char[] modelStr) {
        //next记录的是个数，不是下标
        if (0 == i) {
            return 0;
        }
        int last = next[i -1];
        //没有匹配的,直接判断第一个是否匹配
        if (0 == last) {
            if (modelStr[last] == modelStr[i]) {
                return 1;
            }
            return 0;
        }
        //如果last不为0，有值，可以作为最长匹配的前缀
        if (modelStr[last] == modelStr[i]) {
            return next[i - 1] + 1;
        }
        //当next[i-1]对应的子串的下一个值与modelStr不匹配时，需要找到当前要找的最长匹配子串的次长子串
        //依据就是次长子串对应的子串的下一个字符==modelStr[i];
        int tempIndex = i;
        while (tempIndex > 0) {
            last = next[tempIndex - 1];
            //找到第一个下一个字符是当前字符的匹配子串
            if (modelStr[last] == modelStr[i]) {
                return last + 1;
            }
            -- tempIndex;
        }
        return 0;
    }

を設定して開始する必要があります。次の配列Matchを使用して、先頭の文字からマッチングを開始し、最初の不一致文字を探します。このとき、それまでのものはすべて一致します。次に、最初に完全一致かどうかを判断します。直接リターンの場合、そうでない場合は、最初の文字が一致するかどうかを判断し、一致しない場合は、次の文字に直接一致します。適切なプレフィックスがある場合は、この時点で次の配列が使用されます。次の配列を通じて、現在の一致がどこから開始できるかがわかり、以前のものと一致する必要はありません。

rree

以上がJavaでのKMPアルゴリズムの実装方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。