POJ 3773 - String-Matching Automata

http://poj.org/problem?id=3773

概要

与えられた文字列にマッチするようなオートマトンを構成したときの遷移表を答える。

制約

解法

辞書の文字列が1つと考えると Aho Corasick 法がそのまま使える。

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 struct AhoCorasick/*{{{*/
  7 {
  8   struct node {
  9     int id;
 10     node *failure;
 11     node *edge[26];
 12     vector<int> accepted;
 13 
 14     ~node() {
 15       for (int i = 0; i < 26; i++) {
 16         if (edge[i] != this) {
 17           delete edge[i];
 18         }
 19       }
 20     }
 21   };
 22 
 23   node *root;
 24 
 25   AhoCorasick(const vector<string> words) : root(new node())
 26   {
 27     root->id = 0;
 28     // build trie
 29     for (vector<string>::const_iterator it = words.begin(); it != words.end(); ++it) {
 30       node *u = root;
 31       for (string::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
 32         const int idx = *jt - 'a';
 33         if (!u->edge[idx]) {
 34           u->edge[idx] = new node();
 35           u->edge[idx]->id = jt - it->begin() + 1;
 36         }
 37         u = u->edge[idx];
 38       }
 39       u->accepted.push_back(it - words.begin());
 40     }
 41 
 42     // build failure link
 43     root->failure = 0;
 44     queue<node *> q;
 45     for (int i = 0; i < 26; i++) {
 46       if (root->edge[i]) {
 47         node *next = root->edge[i];
 48         q.push(next);
 49         next->failure = root;
 50       } else {
 51         root->edge[i] = root;
 52       }
 53     }
 54     while (!q.empty()) {
 55       node *u = q.front();
 56       q.pop();
 57       for (int i = 0; i < 26; i++) {
 58         node *next = u->edge[i];
 59         if (next) {
 60           q.push(next);
 61           node *rev = u->failure;
 62           while (!rev->edge[i]) {
 63             rev = rev->failure;
 64           }
 65           next->failure = rev->edge[i];
 66           const vector<int> &v = next->failure->accepted;
 67           for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
 68             next->accepted.push_back(*it);
 69           }
 70         }
 71       }
 72     }
 73   }
 74 
 75   ~AhoCorasick() {
 76     delete root;
 77   }
 78 
 79   node *next_node(node *u, char c) const
 80   {
 81     const int idx = c-'a';
 82     while (!u->edge[idx]) {
 83       u = u->failure;
 84     }
 85     return u->edge[idx];
 86   }
 87 };/*}}}*/
 88 
 89 int main()
 90 {
 91   ios::sync_with_stdio(false);
 92   string s;
 93   while (getline(cin, s) && s != "0") {
 94     const vector<string> words(1, s);
 95     const int M = s.size();
 96     AhoCorasick ac(words);
 97     AhoCorasick::node *u = ac.root;
 98     for (int i = 0; i <= M; i++) {
 99       cout << i;
100       for (int j = 0; j < 26; j++) {
101         AhoCorasick::node *t = ac.next_node(u, 'a'+j);
102         cout << " " << t->id;
103       }
104       cout << endl;
105       if (i < M) {
106         u = ac.next_node(u, s[i]);
107       }
108     }
109   }
110   return 0;
111 }
poj/3773.cc