同じテキストを繰り返し検索するC++プログラム（データ構造を構築して聖書などを高速検索）

同じテキスト（例えば聖書のような大規模な文書）の中から、指定したパターンを繰り返し検索するC++プログラムを紹介します。このプログラムでは、単純な文字列照合アルゴリズム（力まかせ探索・ナイーブ法）を用いて、パターンが一致するすべての位置を検出し、出現回数をカウントします。

アルゴリズム

開始
    検索対象の元の文字列と検索パターンを入力として受け取る
    org_len ← 元の文字列の長さを格納
    pat_len ← パターンの長さを格納
    for i = 0 to (org_len - pat_len)
        for j = 0 to pat_len - 1
            if (org[i + j] != patt[j])
                break
        if (j == pat_len)
            m をインクリメント
    パターンが見つかった位置を出力
    if (m == 0)
        「一致する箇所は見つかりませんでした」と出力
    else
        見つかった出現総数を出力
    return 0
終了

アルゴリズムのポイント

このアルゴリズムは、元の文字列の先頭から順に、パターンと同じ長さの部分文字列を取り出して比較していく方法です。内側のループで1文字でも不一致があれば直ちに break して次の位置へ移るため、無駄な比較を省けます。内側のループが最後まで完了した場合（j == pat_len）はパターン全体が一致したことを意味し、カウンター m を増やしてその位置を記録します。

計算量は最悪の場合 O(n×m)（n は元の文字列の長さ、m はパターンの長さ）となりますが、実装が非常にシンプルで、短いテキストや単純な用途には十分実用的です。より大規模なテキストを高速に検索したい場合は、KMP法やBoyer-Moore法など、事前にデータ構造を構築する高度な文字列照合アルゴリズムを検討するとよいでしょう。

サンプルコード

#include<iostream>
#include<string.h>
using namespace std;
int main() {
    char org[150], patt[150];
    int i, j, m = 0, org_len, pat_len;
    cout << "\nEnter Original String:";
    cin >> org;
    cout << "Enter Pattern to Search:";
    cin >> patt;
    org_len = strlen(org); // 元の文字列の長さを格納
    pat_len = strlen(patt); // パターンの長さを格納
    for (i = 0; i <= (org_len - pat_len); i++) {
        for (j = 0; j < pat_len; j++) {
            if (org[i + j] != patt[j])
                break;
        }
        if (j == pat_len) {
            m++;
            cout << "\nPattern Found at Position: " << i;
        }
    }
    if (m == 0)
        cout << "\nNo Match Found.";
    else
        cout << "\nTotal Number of Instances Found = " << m;
    return 0;
}

実行結果

Enter Original String:thisistutorialspoint.thisisac++program
Enter Pattern to Search:is

Pattern Found at Position: 2
Pattern Found at Position: 4
Pattern Found at Position: 23
Pattern Found at Position: 25
Total Number of Instances Found = 4

実行結果の解説

入力文字列 thisistutorialspoint.thisisac++program の中からパターン is を検索すると、位置2、4、23、25の4箇所で一致が見つかりました。このように、同じテキストに対して何度でも異なるパターンで検索を実行できるため、辞書検索や文書内の語句カウントなど、さまざまな用途に応用できます。