ナイーブ（素朴な）パターン検索アルゴリズムの解説：仕組み・計算量・C++実装例

ナイーブパターン検索とは

ナイーブパターン検索（Naïve Pattern Search）は、数ある文字列探索アルゴリズムの中で最もシンプルな手法です。テキスト（対象となる主文字列）の各文字を、パターン（探したい文字列）と一つずつ照合していくことで、部分文字列を見つけ出します。

このアルゴリズムには、以下のような特徴があります。

• 事前処理（プリプロセッシング）が一切不要
• 短いテキストに対して有効
• 追加のメモリ領域（補助記憶域）を必要としない
• 実装が非常に簡単で分かりやすい

一方で、計算量は O(m×n)（m はパターンの長さ、n は主文字列の長さ）となるため、大規模なテキストには向いていません。効率より simplicity を重視した基本的な探索方法と言えます。

入力と出力の例

入力:
主文字列: "ABAAABCDBBABCDDEBCABC"、パターン: "ABC"
出力:
パターンが見つかった位置: 4
パターンが見つかった位置: 10
パターンが見つかった位置: 18

アルゴリズム

naivePatternSearch(pattern, text)

入力 − テキスト（主文字列）とパターン

出力 − パターンがテキスト内に存在する位置（複数の場合はすべて）

Begin
    patLen := パターンのサイズ
    strLen := 文字列のサイズ

    for i := 0 to (strLen - patLen), do
        for j := 0 to patLen, do
            if text[i+j] ≠ pattern[j], then
                内側のループを抜ける
        done

        if j == patLen, then
            パターンが見つかったので位置 i を表示
    done
End

処理の流れ

1. テキストの先頭から順に、パターンが入り得るすべての開始位置（0 ～ n−m）について調べます。
2. 各開始位置から、パターンの文字を一つずつ比較します。
3. 不一致の文字があればその位置での照合を打ち切り、次の開始位置へ移ります。
4. パターンの最後まで一致した場合、その開始位置を出力します。

C++による実装例

#include<iostream>
using namespace std;

void naivePatternSearch(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();

    for(int i = 0; i<=(strLen - patLen); i++) {
        int j;
        for(j = 0; j<patLen; j++) {      // パターンの各文字が一致するか確認
            if(mainString[i+j] != pattern[j])
                break;
        }

        if(j == patLen) {   // パターンが見つかった場合
            (*index)++;
            array[(*index)] = i;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    naivePatternSearch(mainString, pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

実行結果

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

まとめ

ナイーブパターン検索は、追加メモリ不要・事前処理不要という手軽さが魅力の基本アルゴリズムです。ただし時間計算量が O(m×n) と非効率なため、実用上は KMP 法や Boyer–Moore 法など、より高度な文字列照合アルゴリズムが使われることが一般的です。まずはこの単純な手法で文字列探索の基礎を理解し、その後効率化されたアルゴリズムへ学習を進めるのがおすすめです。