Algoogle

Algorithm for Programming Contest

Aho-Corasick法

基本情報


計算量
用途 入力文字列に対してマッチするパターンを検索

N := 入力文字列の長さ
M := パターンの文字列の長さの合計

解説


まず各パターンからトライ木を作成する.
トライ木というのは例えば6つの文字列{a, ab, aca, ba, c, cab}に対して以下のような木のこと.
trie_tree
この木は文字列の頭に{a, ab, aca, ba, c, cab}に一致するものがあるか根から順に追うことで調べることができる.
例えabcという文字列はroot->a->abまでいけるのでaとabが先頭にあることがわかる.
Aho-Corasick法では, このトライ木を利用してで入力文字列の連続している部分文字列にパターンに一致するものがあるか, またそれは何かを文字列を先頭から順に見るだけで調べることを可能にする.

トライ木の各ノードまでで構成される文字列について, その文字列の末尾と一致するノードのうち長さが最大のノードに辺を張る. もし存在しなければルートに張ることになる.
これは幅優先探索によって容易に実装できる. 以下はそれらの辺を張った後のトライ木. またパターンと一致するノードを灰色に塗ってある.
suffix_link
しかしこのままだと短い文字列に一致していてもわからない場合があるので(例えばcabまで一致したとき, abに辺を張るがaには張らないので見落とす), 各ノードはその祖先が一致した文字列の情報も持つようにする.

コード


(aho_corasick.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;

struct PMA {
    PMA* next[256];
    vector<int> matched;
    PMA() { memset(next, 0, sizeof(next)); }
    ~PMA() { for(int i = 0; i < 256; i++) if(next[i]) delete next[i]; }
};

vector<int> set_union(const vector<int> &a,const vector<int> &b) {
    vector<int> res;
    set_union(all(a), all(b), back_inserter(res));
    return res;
}

PMA *buildPMA(vector<string> pattern) {
    PMA *root = new PMA, *now;
    root->next[0] = root;
    for(int i = 0; i < pattern.size(); i++) {
        now = root;
        for(int j = 0; j < pattern[i].size(); j++) {
            if(now->next[(int)pattern[i][j]] == 0)
                now->next[(int)pattern[i][j]] = new PMA;
            now = now->next[(int)pattern[i][j]];
        }
        now->matched.push_back(i);
    }

    queue<PMA*> que;
    for(int i = 1; i < 256; i++) {
        if(!root->next[i]) root->next[i] = root;
        else {
            root->next[i]->next[0] = root;
            que.push(root->next[i]);
        }
    }
    while(!que.empty()) {
        now = que.front(); que.pop();
        for(int i = 1; i < 256; i++) {
            if(now->next[i]){
                PMA *nxt = now->next[0];
                while(!nxt->next[i]) nxt = nxt->next[0];
                now->next[i]->next[0] = nxt->next[i];
                now->next[i]->matched = set_union(now->next[i]->matched, nxt->next[i]->matched);
                que.push(now->next[i]);
            }
        }
    }
    return root;
}

void match(PMA* &pma, const string s, vector<int> &res) {
    for(int i = 0; i < s.size(); i++){
        int c = s[i];
        while(!pma->next[c])
            pma = pma->next[0];
        pma = pma->next[c];
        for(int j = 0; j < pma->matched.size(); j++)
            res[pma->matched[j]] = true;
    }
}

問題


Comments