C# で KMP アルゴリズムを実装する方法

KMP アルゴリズムを C で実装する方法

#KMP (Knuth-Morris-Pratt) アルゴリズムは、テキスト文字列の一致に使用される効率的な文字列一致アルゴリズムです。のパターン文字列。その中心となる考え方は、一致した部分情報を使用して不必要な比較を避けることです。

KMP アルゴリズムを実装するための鍵は、次の配列とも呼ばれる部分一致テーブル (部分一致テーブル) を構築することです。この配列は、パターン文字列内の各プレフィックス部分文字列の最長一致するサフィックス部分文字列の長さを記録します。

以下は、C# で KMP アルゴリズムを実装するための具体的な手順とコード例です。

ステップ 1: 部分一致テーブルを構築する

1. 次のパターンを定義します。パターン文字列の長さのサイズを整数配列で指定し、next[0] = -1 で初期化します。
2. 2 つのポインター i と j を、それぞれ初期値 0 と -1 で定義します。
3. i がパターン文字列の末尾に到達したかどうかを確認します。到達していない場合は、次の手順を実行します:
   a. j が -1 に等しいか、現在の文字がポインタ j に対応する文字に等しい場合、次に i と j は同時に後方に移動され、 、next[i] = j となります。
   b. それ以外の場合は、ポインタ j を next[j] の位置に移動し、照合を続けます。
4. 次に構築された部分一致テーブルを返します。

上記の手順を実装する方法のコードは次のとおりです。

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

ステップ 2: 部分一致テーブルを使用してマッチングを行う

1. 2 つのポインターを定義するi と j は、それぞれテキスト文字列とパターン文字列の開始位置を指します。
2. i と j が最後に到達したかどうかを確認します。到達していない場合は、次の手順を実行します:
   a. j が -1 に等しい場合、または現在の文字がポインタ j に対応する文字に等しい場合、その場合、i と j は同時に後方に移動します。
   b. それ以外の場合は、ポインタ j を next[j] の位置に移動し、照合を続けます。
3. ポインタ j がパターン文字列の末尾を指している場合、一致が成功し、テキスト文字列の開始位置のインデックスが返されることを意味します。
4. 一致に失敗した場合は、-1 が返されます。

上記の手順を実装するコードは次のとおりです。

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

KMP メソッドを呼び出し、テキスト文字列とパターン文字列を渡すことで、一致する結果を取得できます。 。

上記は、C# で KMP アルゴリズムを実装する方法の手順とコード例です。 KMP アルゴリズムは、部分一致テーブルを利用することで、特に大きなテキスト文字列や長いパターン文字列を処理する場合に、文字列一致の効率を効果的に向上させ、パフォーマンスを向上させることができます。

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