C++で実装する有限オートマトン（Finite Automata）によるパターン検索アルゴリズム

本記事では、文字列の中から特定のパターンを効率的に探し出す「有限オートマトン（Finite Automata）」アルゴリズムを、C++で実装する方法を解説します。

長さ n のテキスト text[0...n-1] と、長さ m のパターン pattern[0...m-1] が与えられたとき、テキスト内にパターンが出現するすべての位置（インデックス）を見つけるのが目的です。

有限オートマトン法の基本的な考え方

このアルゴリズムでは、まず前処理としてパターンから「状態遷移表」を作成します。これは、現在の状態と読み込んだ文字に応じて、次にどの状態へ遷移するかを表す2次元配列です。

遷移表さえ完成していれば、あとはテキストを先頭から1文字ずつ読み込みながら、オートマトンの状態を順番にたどっていくだけです。状態がパターンの長さ m に到達した時点で、パターンが一致したことが分かります。

アルゴリズムの流れ

• パターンをもとに、各状態・各入力文字に対する次の状態を求める関数を定義する。
• 状態数（0〜m）× 文字種（256種類）の遷移表 TF を構築する。
• テキストを走査し、遷移表に従って状態を更新していく。
• 状態が m になったら、その位置（i - m + 1）を出力する。

C++による実装例

#include<stdio.h>
#include<string.h>
#define total_chars 256
int calc_nextstate(char *pat, int M, int state, int x) {
    if (state < M && x == pat[state])
        return state+1;
    int ns, i;
    for (ns = state; ns > 0; ns--) {
        if (pat[ns-1] == x) {
            for (i = 0; i < ns-1; i++)
                if (pat[i] != pat[state-ns+1+i])
                    break;
            if (i == ns-1)
                return ns;
        }
    }
    return 0;
}
//builds Finite Automata
void calc_TF(char *pat, int M, int TF[][total_chars]) {
    int state, x;
    for (state = 0; state <= M; ++state)
        for (x = 0; x < total_chars; ++x)
            TF[state][x] = calc_nextstate(pat, M, state, x);
}
//prints all occurrences of pattern in text
void calc_occur(char *pat, char *txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    int TF[M+1][total_chars];
    calc_TF(pat, M, TF);
    int i, state=0;
    for (i = 0; i < N; i++){
        state = TF[state][txt[i]];
        if (state == M)
            printf ("\n Given pattern is found at the index%d",i-M+1);
    }
}
int main() {
    char *txt = "AABCDAABBDCAABADAABDABAABA";
    char *pat = "AABA";
    calc_occur(pat, txt);
    return 0;
}

実行結果

Given pattern is found at the index 11
Given pattern is found at the index 22

この例では、テキスト "AABCDAABBDCAABADAABDABAABA" の中に、パターン "AABA" がインデックス 11 と 22 の位置で一致していることが確認できます。

計算量について

遷移表の構築には、状態数 m × 文字種 256 回だけ次状態の計算が必要なため、O(m × 256) の時間がかかります。一方、テキストの走査は各文字につき遷移表を1回参照するだけなので、O(n) で完了します。

つまり全体の計算量は O(m × 256 + n) となり、同じパターンで多数のテキストを検索する場合など、前処理コストを事前に払っておくことで高速な照合が可能になるのが、この手法の大きな利点です。