C言語で学ぶナイーブ文字列パターン検索アルゴリズムの実装方法

C言語におけるパターンマッチングとは、ある文字列の中に別の文字列が含まれているかどうかを調べる処理のことです。例えば、「naive algorithm」という文字列の中に「algorithm」という文字列が存在するかを確認し、見つかった場合はその位置（インデックス）を表示します。本記事では、2つの文字配列を受け取り、一致が見つかればその位置を返し、見つからなければ -1 を返す関数を作成する方法を解説します。

入力例と出力例

入力: txt = "HERE IS A NICE CAP"
　　　pattern = "NICE"
出力: パターンはインデックス10で見つかりました

入力: txt = "XYZXACAADXYZXYZX"
　　　pattern = "XYZX"
出力: パターンはインデックス0で見つかりました
　　　パターンはインデックス9で見つかりました
　　　パターンはインデックス12で見つかりました

この問題はナイーブ（素朴）パターン検索によって解決します。このアルゴリズムは、比較的小さなテキストに対して有効です。ナイーブ法は非常にシンプルな手法で、一方の文字列がもう一方の文字列のどこに出現するかを調べるために、考えられるすべての位置を一つずつ順番に確認していくというものです。

ナイーブアルゴリズムの時間計算量は O(mn) です。ここで m は検索対象となるパターンのサイズ、n は検索先となる元の文字列のサイズを表します。

パターン検索は、コンピュータサイエンスにおいて非常に重要な問題の一つです。テキストエディタやワープロソフト、ブラウザ、データベースなどで文字列を検索する際には、必ずと言っていいほどパターン検索アルゴリズムが使われており、その検索結果の表示を支えています。

アルゴリズムの手順

naive_algorithm(pattern, text)

入力 − 検索対象のテキストとパターン

出力 − パターンがテキスト内に存在する位置

開始
　　pat_len := パターンのサイズ
　　str_len := 文字列のサイズ
　　for i := 0 to (str_len - pat_len), do
　　　　for j := 0 to pat_len, do
　　　　　　if text[i+j] ≠ pattern[j], then
　　　　　　　　break
　　if j == pat_len, then
　　　　パターンが見つかった位置 i を表示
終了

このアルゴリズムでは、テキストの先頭から順にパターンとの照合を試みます。各位置において、パターンの文字を先頭から1文字ずつ比較し、不一致があれば次の位置へ移動します。パターン全体が一致した場合、その開始位置を出力します。

C言語での実装例

#include <stdio.h>
#include <string.h>

int main() {
    char txt[] = "tutorialsPointisthebestplatformforprogrammers";
    char pat[] = "a";
    int M = strlen(pat);
    int N = strlen(txt);

    for (int i = 0; i <= N - M; i++) {
        int j;
        for (j = 0; j < M; j++)
            if (txt[i + j] != pat[j])
                break;
        if (j == M)
            printf("Pattern matches at index %d \n", i);
    }
    return 0;
}

実行結果

Pattern matches at index 6
Pattern matches at index 25
Pattern matches at index 39

このプログラムでは、文字列「tutorialsPointisthebestplatformforprogrammers」の中から文字「a」を検索しています。外側のループでテキストの各位置を走査し、内側のループでパターンとの一致を確認しています。変数 j がパターンの長さ M に達していれば、その位置で完全一致があったことを意味します。

ナイーブ法の特徴と注意点

ナイーブパターン検索は実装が簡単で理解しやすい反面、最悪の場合 O(mn) の計算量が必要となり、大きなテキストに対しては非効率になることがあります。より大規模なテキストを高速に処理したい場合は、KMP法（Knuth–Morris–Pratt法）やボイヤー・ムーア法といった、より高度な文字列検索アルゴリズムの利用を検討するとよいでしょう。ただし、短い文字列や単純な用途であれば、ナイーブ法でも十分に実用的です。