POJ 1204 AC自动机

链接：

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

题意：

给定一个n*m的大写字母组成的矩阵，再给定C个单词，这些单词可能出现在矩阵中，出现的方向可能是上、下、左、右、左上、右上、左下、右下

问这C个单词的第一个字母出现在矩阵中的什么位置，以及出现的方向。

题解：

这题有两种解法，第一种是用字典树+深搜，用单词建立一颗字典树，然后八个方向去深搜，很容易想也很容易写，这种方法在数据很给力的的时候就会超时，所以不多讲。

第二种方法是AC自动机，在AC自动机题目中算比较常规的字符串匹配问题。

由于要记录每个单词单词在矩阵的第一个字母顺序和方向，这有些困难，因为在匹配的过程中初始没办法回溯求初始位置，硬要这样的话肯定也行，比较麻烦。

考虑将单词反转，这样就是最后匹配到的那个位置，这样就不要回溯。

建好字典树后改装成AC自动机，然后在矩阵中从12个方向去查询，如果遇到危险节点（某个单词在这里结束）就可以记录这个单词的位置和方向了。

这里并不需要记录12个方向的字符串，只要在查询的过程按照某个方向一直走就好。

代码：

 31 int n, m, w;
 32 string s[MAXN];
 33 int pos[MAXN][3];
 34 int dir[8][2] = { 0,1,0,-1,1,0,-1,0,1,1,-1,-1,1,-1,-1,1 };
 35 char ch[9] = "CGEADHFB";
 36 int head, tail;
 37 
 38 struct node {
 39     node *fail;
 40     node *next[26];
 41     int id;
 42     node() {
 43         fail = NULL;
 44         id= 0;
 45         rep(i, 0, 26) next[i] = NULL;
 46     }
 47 }*q[1000010];
 48 node *root;
 49 
 50 void insert(string s, int id) {
 51     node *p = root;
 52     int len = s.length();
 53     rep(i, 0, len) {
 54         int temp = s[i] - 'A';
 55         if (p->next[temp] == NULL) p->next[temp] = new node();
 56         p = p->next[temp];
 57     }
 58     p->id = id;
 59 }
 60 
 61 void build_ac() {
 62     q[tail++] = root;
 63     while (head != tail) {
 64         node *p = q[head++];
 65         node *temp = NULL;
 66         rep(i, 0, 26) if (p->next[i] != NULL) {
 67             if (p == root) p->next[i]->fail = root;
 68             else {
 69                 temp = p->fail;
 70                 while (temp != NULL) {
 71                     if (temp->next[i] != NULL) {
 72                         p->next[i]->fail = temp->next[i];
 73                         break;
 74                     }
 75                     temp = temp->fail;
 76                 }
 77                 if (temp == NULL) p->next[i]->fail = root;
 78             }
 79             q[tail++] = p->next[i];
 80         }
 81     }
 82 }
 83 
 84 void query(int x, int y, int d, int id) {
 85     node *p = root;
 86     while (x >= 0 && x < n && y >= 0 && y < m) {
 87         int index = s[x][y] - 'A';
 88         while (p->next[index] == NULL && p != root) p = p->fail;
 89         p = p->next[index];
 90         if (p == NULL) p = root;
 91         node *temp = p;
 92         while (temp != root && temp->id) {
 93             int k = temp->id;
 94             if (pos[k][0] > x || pos[k][0] == x && pos[k][1] > y)
 95                 pos[k][0] = x, pos[k][1] = y, pos[k][2] = id;
 96             temp = temp->fail;
 97         }
 98         x += dir[d][0];
 99         y += dir[d][1];
100     }
101 }
102 
103 int main() {
104     ios::sync_with_stdio(false), cin.tie(0);
105     cin >> n >> m >> w;
106     root = new node(); 
107     rep(i, 0, n) cin >> s[i];
108     rep(i, 1, w + 1) {
109         string a;
110         cin >> a;
111         reverse(all(a));
112         insert(a, i);
113         pos[i][0] = pos[i][1] = INF;
114     }
115     build_ac();
116     rep(i, 0, n) {
117         query(i, 0, 0, 1), query(i, m - 1, 1, 0);
118         query(i, 0, 7, 6), query(i, m - 1, 6, 7);
119         query(i, 0, 4, 5), query(i, m - 1, 5, 4);
120     }
121     rep(i, 0, m) {
122         query(0, i, 2, 3), query(n - 1, i, 3, 2);
123         query(0, i, 6, 7), query(n - 1, i, 7, 6);
124         query(0, i, 4, 5), query(n - 1, i, 5, 4);
125     }
126     rep(i, 1, w + 1)
127         cout << pos[i][0] << ' ' << pos[i][1] << ' ' << ch[pos[i][2]] << endl;
128     return 0;
129 }