複数パターン検索 (Aho-Corasick)

説明

複数のパターン文字列からなる集合と長い文字列が与えられる．長い文字列に対してマッチするパターン文字列をすべて求めるアルゴリズムが Aho Corasick である．これは複数パターン文字列をあらかじめ trie に変換してから KMP を実行し，パターンマッチング・オートマトンを構成していることになる．

詳しくは適当な成書や http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf などを参考のこと．

計算量

• 構築 O(m)．
• 検索 O(n + m)．

ただし m はパターンの文字列長の総和，n は検索テキスト長．

使い方

struct PMA; を適宜設定のこと．

buildPMA(char *p[], int m)

0 ... m-1 の複数の検索パターンから，パターンマッチング・オートマトンを構築する．

match(char *t, PMA *v, int result[])

t を PMA に流し込む．result[k] には p[k] が t に何回現れたかが入る．

ソースコード

struct PMA {
  PMA *next[0x100]; // next[0] is for fail
  vector<int> accept;
  PMA() { fill(next, next+0x100, (PMA*)0); }
};
PMA *buildPMA(char *p[], int size) {
  PMA *root = new PMA;
  for (int i = 0; i < size; ++i) { // make trie
    PMA *t = root;
    for (int j = 0; p[i][j]; ++j) {
      char c = p[i][j];
      if (t->next[c] == NULL) t->next[c] = new PMA;
      t = t->next[c];
    }
    t->accept.push_back(i);
  }
  queue<PMA*> Q; // make failure link using bfs
  for (int c = 'a'; c <= 'z'; ++c) {
    if (root->next[c]) {
      root->next[c]->next[0] = root;
      Q.push(root->next[c]);
    } else root->next[c] = root;
  }
  while (!Q.empty()) {
    PMA *t = Q.front(); Q.pop();
    for (int c = 'a'; c <= 'z'; ++c) {
      if (t->next[c]) {
        Q.push(t->next[c]);
        PMA *r = t->next[0];
        while (!r->next[c]) r = r->next[0];
        t->next[c]->next[0] = r->next[c];
      }
    }
  }
  return root;
}
int match(char *t, PMA *v, int *result) {
  int n = strlen(t);
  int count = 0;
  for (int i = 0; i < n; ++i) {
    char c = t[i];
    while (!v->next[c]) v = v->next[0];
    v = v->next[c];
    for (int j = 0; j < v->accept.size(); ++j)
      result[v->accept[j]]++;
  }
}

Verified

• UVA 10679 (I Love Strings!!), 0.300 s．