文字列検索問題は、与えられたテキスト文字列 S の中にパターン文字列 P が出現する位置をすべて求める課題である。ナイーブな実装では、各位置から一致を確認し、最悪計算量は $O(|S|\; \backslash cdot\; |P|)$ となる。

これを効率化するために、KMP（Knuth-Morris-Pratt）アルゴリズムが用いられる。このアルゴリズムは、マッチング失敗時に無駄な比較を省略することで、線形時間 $O(|S|\; +\; |P|)$ での検索を可能にする。

部分一致テーブル（failure function / π 関数）の構築

KMPの核心は「部分一致テーブル」（以下、pi 配列）にある。この配列は、パターン文字列 P の各接頭辞について、「真の接頭辞かつ真の接尾辞」となる最長共通部分の長さを記録する。

例えば、P = "ababc" の場合、各位置における pi[i] は以下のようになる：

• pi[0] = 0（1文字目には真の接頭辞・接尾辞なし）
• pi[1] = 0（"ab" → 共通なし）
• pi[2] = 1（"aba" → "a"）
• pi[3] = 2（"abab" → "ab"）
• pi[4] = 0（"ababc" → 共通なし）

このテーブルは次のように構築される：

vector<int> compute_pi(const string& pattern) {
    int n = pattern.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j])
            j = pi[j - 1];
        if (pattern[i] == pattern[j])
            ++j;
        pi[i] = j;
    }
    return pi;
}

マッチング処理

テキスト S を走査しながら、現在のマッチ長 j を管理する。文字が一致すれば j を進め、不一致時は pi[j - 1] を用いて適切な位置にジャンプする。

完全一致（j == |P|）が発生した場合、その開始位置を記録し、j = pi[j - 1] として次のマッチングを継続する。

void kmp_search(const string& text, const string& pattern) {
    auto pi = compute_pi(pattern);
    int n = text.size(), m = pattern.size();
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j])
            j = pi[j - 1];
        if (text[i] == pattern[j])
            ++j;
        if (j == m) {
            cout << i - m + 2 << '\n'; // 1-indexed 出力
            j = pi[j - 1];
        }
    }
}

上記実装により、テキスト全体を一回だけ走査しつつ、パターンの全出現位置を効率的に検出できる。