POJ 1204 - Word Puzzles

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

概要

\(L \times C\) の表が与えられ、各セルには大文字のアルファベットが書かれている。 \(W\) 個の単語が与えられるので、各単語が表中のどの位置から、縦・横・斜めのどの方向に向かって存在するかを答える。

制約

解法

Aho-Corasick 法の練習。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <vector>
  4 #include <queue>
  5 using namespace std;
  6 
  7 struct ans
  8 {
  9   int i, j, dir;
 10   ans() : i(-1), j(-1), dir(-1) {}
 11   ans(int a, int b, int c) : i(a), j(b), dir(c) {}
 12 };
 13 
 14 int L, C;
 15 char grid[1000][1000];
 16 ans ret[1000];
 17 static const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
 18 static const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
 19 
 20 struct AhoCorasick
 21 {
 22   struct node {
 23     node *failure;
 24     node *edge[26];
 25     vector<int> accepted;
 26 
 27     ~node() {
 28       for (int i = 0; i < 26; i++) {
 29         if (edge[i] != this) {
 30           delete edge[i];
 31         }
 32       }
 33     }
 34   };
 35 
 36   node *root;
 37 
 38   AhoCorasick(const char words[1000][1001], int W)
 39     : root(new node())
 40   {
 41     // build trie
 42     for (int i = 0; i < W; i++) {
 43       const char *s = words[i];
 44       node *u = root;
 45       for (int j = 0; s[j] != '\0'; j++) {
 46         const int idx = s[j] - 'A';
 47         if (!u->edge[idx]) {
 48           u->edge[idx] = new node();
 49         }
 50         u = u->edge[idx];
 51       }
 52       u->accepted.push_back(i);
 53     }
 54 
 55     // build failure link
 56     root->failure = 0;
 57     queue<node *> q;
 58     for (int i = 0; i < 26; i++) {
 59       if (root->edge[i]) {
 60         node *next = root->edge[i];
 61         q.push(next);
 62         next->failure = root;
 63       } else {
 64         root->edge[i] = root;
 65       }
 66     }
 67     while (!q.empty()) {
 68       node *u = q.front();
 69       q.pop();
 70       for (int i = 0; i < 26; i++) {
 71         node *next = u->edge[i];
 72         if (next) {
 73           q.push(next);
 74           node *rev = u->failure;
 75           while (!rev->edge[i]) {
 76             rev = rev->failure;
 77           }
 78           next->failure = rev->edge[i];
 79           const vector<int> &v = next->failure->accepted;
 80           for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
 81             next->accepted.push_back(*it);
 82           }
 83         }
 84       }
 85     }
 86   }
 87 
 88   ~AhoCorasick() {
 89     delete root;
 90   }
 91 
 92   void match(int i, int j, int d) const
 93   {
 94     node *u = root;
 95     for (; 0 <= i && i < L && 0 <= j && j < C; i += di[d], j += dj[d]) {
 96       const int idx = grid[i][j] - 'A';
 97       while (!u->edge[idx]) {
 98         u = u->failure;
 99       }
100       u = u->edge[idx];
101       for (vector<int>::const_iterator jt = u->accepted.begin(); jt != u->accepted.end(); ++jt) {
102         ret[*jt] = ans(i, j, d);
103       }
104     }
105   }
106 };
107 
108 int main()
109 {
110   int W;
111   scanf("%d %d %d", &L, &C, &W);
112   for (int i = 0; i < L; i++) {
113     scanf("%s", grid[i]);
114   }
115   static char words[1000][1001];
116   for (int i = 0; i < W; i++) {
117     scanf("%s", words[i]);
118   }
119 
120   AhoCorasick ac(words, W);
121   for (int i = 0; i < L; i++) {
122     ac.match(i, 0, 1);
123     ac.match(i, 0, 2);
124     ac.match(i, 0, 3);
125     ac.match(i, C-1, 5);
126     ac.match(i, C-1, 6);
127     ac.match(i, C-1, 7);
128   }
129   for (int j = 0; j < C; j++) {
130     ac.match(L-1, j, 7);
131     ac.match(L-1, j, 0);
132     ac.match(L-1, j, 1);
133     ac.match(0, j, 3);
134     ac.match(0, j, 4);
135     ac.match(0, j, 5);
136   }
137 
138   for (int i = 0; i < W; i++) {
139     const ans& a = ret[i];
140     const int n = strlen(words[i]) - 1;
141     printf("%d %d %c\n", a.i - di[a.dir]*n, a.j - dj[a.dir]*n, 'A' + a.dir);
142   }
143   return 0;
144 }
poj/1204.cc