総当たり照合の計算量課題

テキスト内の特定パターンを検索する最も単純な手法は、テキストの各位置を開始点とみなし、パターンと逐次比較する総当たり法です。このアプローチは実装が容易ですが、最悪ケースではテキスト長を $N$、パターン長を $M$ とした場合、$O(NM)$ の計算量を要します。反復比較の重複を排除し、線形時間へ改善するための基礎的な手法がKMP（Knuth-Morris-Pratt）アルゴリズムです。

#include <string>
#include <iostream>

int naive_search(const std::string& text, const std::string& pat) {
    int hits = 0;
    const int n = static_cast<int>(text.length());
    const int m = static_cast<int>(pat.length());
    
    for (int head = 0; head <= n - m; ++head) {
        bool aligned = true;
        for (int offset = 0; offset < m; ++offset) {
            if (text[head + offset] != pat[offset]) {
                aligned = false;
                break;
            }
        }
        if (aligned) ++hits;
    }
    return hits;
}

KMPによる照合処理の最適化

KMPアルゴリズムの核心は、ミスマッチ発生時にテキストの走査位置を後退させず、既知の一致情報を利用してパターンの照合位置を適切にジャンプさせる点にあります。これを制御するのが「部分一致テーブル（接頭辞関数）」です。テーブルは、パターンの各接尾辞が自身の接頭辞と一致する最長長を記録します。失配が発生した場合、この値を参照して照合ポインタを前方へ飛ばすことで、冗長な比較を回避します。

void execute_kmp_search(const std::string& text, const std::string& pat, const std::vector<int>& pi) {
    const int n = text.length();
    const int m = pat.length();
    int match_len = 0;
    
    for (int i = 0; i < n; ++i) {
        while (match_len > 0 && text[i] != pat[match_len]) {
            match_len = pi[match_len - 1];
        }
        if (text[i] == pat[match_len]) {
            match_len++;
        }
        if (match_len == m) {
            std::cout << "Match at index: " << (i - m + 1) << "\n";
            match_len = pi[match_len - 1];
        }
    }
}

部分一致テーブルの線形時間構築

照合処理を高速化するには、事前に部分一致テーブルを構築する必要があります。テーブルの生成は、パターンを自身と照合する自己参照プロセスで実現します。現在の一致長を保持しながら、文字が一致すれば長さを伸ばし、不一致であればテーブル値を参照して一致長を縮小する操作を繰り返します。この手続きにより、テーブル構築も $O(M)$ で完了します。

std::vector<int> build_prefix_table(const std::string& pat) {
    const int m = pat.length();
    std::vector<int> pi(m, 0);
    int prefix_len = 0;
    
    for (int curr = 1; curr < m; ++curr) {
        while (prefix_len > 0 && pat[curr] != pat[prefix_len]) {
            prefix_len = pi[prefix_len - 1];
        }
        if (pat[curr] == pat[prefix_len]) {
            prefix_len++;
        }
        pi[curr] = prefix_len;
    }
    return pi;
}

計算量の特性と拡張KMPへの移行

KMP法ではテキストとパターンをそれぞれ一回のみ走査するため、全体の時間計算量は $O(N + M)$ に収まります。`while` ループによる一致長の縮小回数が、増加回数を超えない性質により、実質的な比較回数は定数倍以内に抑えられます。この状態遷移の最適化は、より広範な文字列処理へ発展する基盤となります。拡張KMP（Z法）は、KMPがパターン照合に特化しているのに対し、任意の位置から始まる部分文字列とパターン（または文字列自身の接頭辞）との最長共通長を全位置で一度に算出します。Z配列の構築では、既に計算済みの区間の対称性を活用して未処理領域の比較をスキップし、同様に $O(N + M)$ で処理を完了させます。この枠組みにより、複数パターンの同時検索や回文判定、文字列の繰り返し構造の検出などが統一的に扱えるようになります。