【C言語】KMPアルゴリズムでパターン検索を行うプログラムの実装方法

この問題では、テキスト(text)とパターン(pattern)という2つの文字列が与えられます。求められているのは、KMP(Knuth Morris Pratt)アルゴリズムを用いたパターン検索プログラムを作成し、テキスト文字列の中にパターンが出現するすべての位置(インデックス)を見つけ出すことです。

それでは、具体的な例を使って問題を確認してみましょう。

入力例

text = "xyztrwqxyzfg" pattern = "xyz"

出力例

Found at index 0
Found at index 7

この例では、テキスト「xyztrwqxyzfg」の中に、パターン「xyz」がインデックス0とインデックス7の2箇所に出現していることが分かります。

KMPアルゴリズムとは

ここでは、KMP(Knuth Morris Pratt)パターン検索アルゴリズムを使った解法について解説します。KMP法は、事前にパターン文字列に対して前処理(preprocessing)を行い、その結果をテキストとの照合に活用する手法です。

単純な全探索(ナイーブな方法)では、照合に失敗するたびにテキスト側の比較位置を1つ戻して再検索するため、最悪の場合 O(N×M) の計算量が必要になります。一方、KMPアルゴリズムは前処理によって得られた情報を利用することで、一度比較した文字を再度比較することなく検索を進められます。そのため、マッチング中に不一致の文字が現れた場合でも、効率よく次の比較位置へ移行できるのが大きな特徴です。

接頭辞・接尾辞配列(LPS配列)の作成

KMP法の鍵となるのは、パターン文字列に対する前処理です。ここでは、パターンの各位置における「適切な接頭辞(proper prefix)」と「接尾辞(suffix)」が一致する最大の長さを記録した配列(一般にLPS配列や失敗関数と呼ばれます)を作成します。この配列があることで、照合中にミスマッチが発生した際、どこまで一致していた情報を再利用できるかがすぐに判断でき、無駄な比較を省くことができます。

C言語によるKMPアルゴリズムの実装

以下が、C言語(C++としてもコンパイル可能)で書かれたKMPアルゴリズムによるパターン検索プログラムの完全なコードです。

サンプルコード

#include<iostream>
#include<string.h>
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
    int length = 0;
    pps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[length]) {
            length++;
            pps[i] = length;
            i++;
        } else {
            if (length != 0)
                length = pps[length - 1];
            else {
                pps[i] = 0;
                i++;
            }
        }
    }
}
void KMPAlgorithm(char* text, char* pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int pps[M];
    prefixSuffixArray(pattern, M, pps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        if (j == M) {
            printf("Found pattern at index %d\n", i - j);
            j = pps[j - 1];
        }
        else if (i < N && pattern[j] != text[i]) {
            if (j != 0)
                j = pps[j - 1];
            else
                i = i + 1;
        }
    }
}
int main() {
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    KMPAlgorithm(text, pattern);
    return 0;
}

コードのポイント

• prefixSuffixArray関数: パターンに対してLPS配列(接頭辞と接尾辞の一致長を格納した配列)を構築します。
• KMPAlgorithm関数: テキストとパターンを先頭から順に比較し、一致した場合は両方のポインタを進めます。パターン全体が一致したら出現位置を出力し、LPS配列を参照して比較を続行します。不一致の場合もLPS配列を活用して、テキスト側のポインタを後戻りさせることなく処理を進めます。

実行結果

上記のプログラムを実行すると、以下のような出力が得られます。

The pattern is found in the text at the following index :
Found pattern at index 0
Found pattern at index 7

このように、KMPアルゴリズムを使用すると、テキスト内にパターンが出現するすべての位置を効率的に検索できます。計算量は前処理にO(M)、検索本体にO(N)となり、全体で O(N + M) と非常に高速であるため、大きなテキストに対する文字列検索に適しています。