C++でベクトル（vector）を使って文字列照合を実装する方法

文字列照合にはさまざまな手法がありますが、本記事ではベクトル（std::vector）を活用した文字列検索の実装方法を解説します。このアプローチでは、検索対象のメイン文字列と、探したいパターン文字列をどちらもベクトルとして扱い、その中から一致する部分を見つけ出します。

C++では、標準ライブラリを利用することでベクトルを簡単に作成・操作できます。まずメイン文字列と検索用のパターン文字列をそれぞれベクトルに格納し、メイン文字列の中からパターンを検索します。一致が見つかると、関数はその位置を返すとともに、処理済みの部分をメイン文字列から削除します。そのため、次の検索では常に残りの文字列に対して処理が続行される仕組みです。

複数箇所でパターンが出現するケースにも対応できるよう、ループ処理によって繰り返しマッチングを実行し、見つかるたびにその位置を出力します。

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

アルゴリズム

vector_pattern_search(main, substr)

入力 − メインテキストと検索対象の部分文字列。

出力 − パターンが見つかった位置。

Begin
    p := メイン文字列の先頭位置
    while r が substr の終端に達しておらず、p が main の終端に達していない間:
        r := substr の先頭位置
        while p と r の指す要素が異なり、p が main の範囲内である間:
            p := p + 1
            i := i + 1
        done
        q := p
        while p と r の指す要素が一致し、r が substr の範囲内かつ p が main の範囲内である間:
            p := p + 1
            i := i + 1
            r := r + 1
        done
        if r が substr の範囲外になった場合:
            main から最初に出現する substr を削除する
            substr が見つかった位置を返す

        if p が main の範囲外になった場合:
            return 0
        q := q + 1
        p := q
    done
End

サンプルコード

以下が、上記アルゴリズムをC++で実装したサンプルプログラムです。getchar()で標準入力から文字を1文字ずつ読み込んでベクトルに格納し、イテレータを使ってパターンとの照合を行っています。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void take_string(vector<char> &string){
    char c;
    while(true){
        c = getchar();
        if(c == '\n'){
            break;
        }
        string.push_back(c);
    }
}

void display(vector<char> string){
    for(int i = 0; i<string.size(); i++){
        cout << string[i];
    }
}

int match_string(vector<char>& main, vector<char> substr){
    vector<char>::iterator p,q, r;
    int i = 0;

    p = main.begin();

    while (r <= substr.end() && p <= main.end()){
        r = substr.begin();
        while (*p != *r && p < main.end()){
            p++;
            i++;
        }
        q = p;

        while (*p == *r && r <= substr.end() && p<=main.end()){
            p++;
            i++;
            r++;
        }

        if (r >= substr.end()){
            main.erase(main.begin(), q + 1);
            return (i - substr.size() + 1);
        }

        if (p >= main.end())
            return 0;
        p = ++q;
    }
}

実行結果

プログラムをコンパイルして実行すると、パターンが見つかった位置が順に出力されます。

Enter main String: C++ is programming language. It is object oriented language
Enter substring to find: language

Match found at Position = 20
Match found at Position = 52

この例では、"language" という単語が20番目と52番目の位置で見つかりました。この実装では、一致が見つかるたびにメイン文字列の先頭から該当部分までが削除されますが、カウンタ i は通算されているため、返される位置は元の文字列における絶対的な位置になります。そのため、関数を繰り返し呼び出すことで、すべての出現箇所を正確に特定できます。