C++で実装する短いテキスト向け文字列検索アルゴリズムの解説

このC++プログラムでは、入力としてテキスト(元の文字列)とパターン(検索したい文字列)を受け取ります。そして、テキストの中からパターンを検索し、見つかったすべての出現位置と合計マッチ数を出力します。

本記事では、単純な二重ループ(総当たり方式)による文字列検索アルゴリズムの考え方と、実際に動作するサンプルコード、実行結果までをわかりやすく解説します。

アルゴリズムの流れ

開始
　　文字列とパターンを入力として受け取る。
　　元の文字列用とパターン用の配列を宣言する。
　　それぞれの長さを len_ori と len_dupli に格納する。
　　ループを使ってパターンが一致する位置を探す。
　　パターンが見つからなければ「見つかりません」と表示し、
　　見つかれば一致した回数を出力する。
終了

処理のポイント

外側のループでテキストの先頭から順に走査位置を移動させ、内側のループでその位置から始まる部分文字列がパターンと完全一致するかを1文字ずつ比較します。すべての文字が一致した場合のみ、その位置を出力対象とします。

サンプルコード

#include<iostream>
#include<cstring>
using namespace std;

int main() {
    char ori[120], dupli[120];
    int i, j, k = 0, len_ori, len_dupli;

    cout<<"空白を含まない文字列を入力してください"<<endl;

    cout<<"\n元の文字列を入力:";
    cin>>ori;

    cout<<"検索するパターンを入力:";
    cin>>dupli;

    len_ori = strlen(ori);
    len_dupli = strlen(dupli);

    // 検索パターンの位置を見つけるためのループ
    for (i = 0; i <= (len_ori - len_dupli); i++) {
        for (j = 0; j < len_dupli; j++) {
            if (ori[i + j] != dupli[j])
            break;
        }
        if (j == len_dupli) {
            k++;
            cout<<"\nパターンが見つかった位置: "<<i;
        }
    }
    if (k == 0)
        cout<<"\n一致するものは見つかりませんでした!";
    else
        cout<<"\n見つかった合計数 = "<<k;
    return 0;
}

実行例

空白を含まない文字列を入力してください

元の文字列を入力:aaaa
検索するパターンを入力:aa

パターンが見つかった位置: 0
パターンが見つかった位置: 1
パターンが見つかった位置: 2
見つかった合計数 = 3

解説と補足

時間計算量: この手法は最悪の場合 O(n × m)(nはテキストの長さ、mはパターンの長さ)となります。短いテキストには十分実用的ですが、大規模なデータではKMP法やBoyer-Moore法などの高速なアルゴリズムが適しています。

注意点: cin >> を使っているため、空白文字を含む文字列は入力できません。空白を含む行全体を読み込みたい場合は cin.getline() の利用を検討してください。