KMP アルゴリズムを C で実装する方法
#KMP (Knuth-Morris-Pratt) アルゴリズムは、テキスト文字列の一致に使用される効率的な文字列一致アルゴリズムです。のパターン文字列。その中心となる考え方は、一致した部分情報を使用して不必要な比較を避けることです。
KMP アルゴリズムを実装するための鍵は、次の配列とも呼ばれる部分一致テーブル (部分一致テーブル) を構築することです。この配列は、パターン文字列内の各プレフィックス部分文字列の最長一致するサフィックス部分文字列の長さを記録します。
以下は、C# で KMP アルゴリズムを実装するための具体的な手順とコード例です。
ステップ 1: 部分一致テーブルを構築する
上記の手順を実装する方法のコードは次のとおりです。
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: 部分一致テーブルを使用してマッチングを行う
上記の手順を実装するコードは次のとおりです。
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 サイトの他の関連記事を参照してください。