AC 自動機は、複数のパターン文字列を効率的に検索するためのアルゴリズムです。この記事では、その基本的な構造と動作原理について説明します。

前提知識

AC 自動機を理解するためには、まずは字典木（Trie木）とKMPアルゴリズムの概念を理解しておく必要があります。

問題設定

KMPアルゴリズムは単一のパターン文字列に対する文字列マッチングを行いますが、複数のパターン文字列に対して効率的にマッチングを行うためにAC自動機を使用します。

AC 自動機の基本構造

AC 自動機は、複数のパターン文字列から構成されるTrie木に失敗リンク（失配ポインタ）を追加したものです。

実装手順

ステップ1: Trie木の構築

まず、各パターン文字列をTrie木に挿入します。各ノードには子ノードへのリンク、失敗リンク、およびパターンの終端を示すフラグが含まれます。

struct Node {
    int fail;
    int children[26];
    bool terminal;
};

Node trie[MAX_NODES];
int node_count = 1;

void insert(const string& pattern) {
    int current = 0;
    for (char c : pattern) {
        int index = c - 'a';
        if (trie[current].children[index] == 0) {
            trie[current].children[index] = node_count++;
        }
        current = trie[current].children[index];
    }
    trie[current].terminal = true;
}

ステップ2: 失敗リンクの計算

BFSを使用して各ノードの失敗リンクを計算します。失敗リンクは、現在のノードの文字に対応する子ノードが存在しない場合に移動すべきノードを示します。

void build_fail_links() {
    queue<int> q;
    for (int i = 0; i < 26; ++i) {
        if (trie[0].children[i] != 0) {
            q.push(trie[0].children[i]);
        } else {
            trie[0].children[i] = 0;
        }
    }
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i) {
            int child = trie[current].children[i];
            if (child != 0) {
                int fail = trie[current].fail;
                while (trie[fail].children[i] == 0 && fail != 0) {
                    fail = trie[fail].fail;
                }
                trie[child].fail = trie[fail].children[i];
                if (trie[trie[child].fail].terminal) {
                    trie[child].terminal = true;
                }
                q.push(child);
            } else {
                trie[current].children[i] = trie[trie[current].fail].children[i];
            }
        }
    }
}

ステップ3: マッチングの実行

与えられたテキストに対してマッチングを行います。現在のノードから始めて、テキストの各文字に対応する子ノードへ遷移し、必要に応じて失敗リンクを使用して次のノードへ移動します。

vector<string> match_patterns(const string& text) {
    vector<string> matches;
    int current = 0;
    for (char c : text) {
        int index = c - 'a';
        while (trie[current].children[index] == 0 && current != 0) {
            current = trie[current].fail;
        }
        current = trie[current].children[index];
        int temp = current;
        while (temp != 0) {
            if (trie[temp].terminal) {
                matches.push_back(text.substr(current - trie[temp].depth, trie[temp].depth));
            }
            temp = trie[temp].fail;
        }
    }
    return matches;
}