POJ_1204

    其实POJ这个题目叙述得不太严谨，所以我就先做SPOJ上这个题去了，回来之后交了一下倒是也过了。

这个题目可以用AC自动机去做，为了能够在匹配完单词后顺利找到单词首位置，我们可以选择把单词反过来建字母树，这样最后一个字符实际上就是第一个字符。

    在后面查找的时候可以做一个小优化，就是找过的字典树上的结点的标记置为-1，以后再遇到这个结点就直接break而没必要再沿着预处理的标记向上寻找了。

#include
     
       #include
      
        #define MAXD 800010 #define MAXN 1010 char b[MAXN][MAXN], word[MAXN]; int N, M, W, next[MAXD][26], flag[MAXD], P[MAXD], q[MAXD], e, dir[MAXN], tx[MAXN], ty[MAXN]; void insert(int cur, int k) {
       ++ e;     flag[e] = 0;     memset(next[e], 0, sizeof(next[e]));     next[cur][k] = e; } void init() {
   int i, j, k, cur; for(i = 0; i < N; i ++)         scanf("%s", b[i]);     e = 0;     memset(next[e], 0, sizeof(next[e])); for(i = 1; i <= W; i ++)     {
           scanf("%s", word);         cur = 0; for(j = strlen(word) - 1; j >= 0; j --)         {
               k = word[j] - 'A'; if(!next[cur][k])                 insert(cur, k);             cur = next[cur][k];         }         flag[cur] = i;     } } void prepare() {
   int i, j, k, u, front, rear;     P[0] = front = rear = 0;     q[rear ++] = 0; while(front < rear)     {
           u = q[front ++]; for(i = 0; i < 26; i ++) if(next[u][i])             {
                   k = next[u][i]; if(u == 0)                     P[k] = 0; else                 {
   for(j = P[u]; j > 0; j = P[j]) if(next[j][i])                         {
                               P[k] = next[j][i]; break;                         } if(j == 0)                         P[k] = next[0][i];                 }                 q[rear ++] = k;             }     } } void deal(int x, int y, int &j, int d) {
   int i, k, t;     k = b[x][y] - 'A'; while(j > 0 && !next[j][k])             j = P[j];     j = next[j][k]; for(t = j; t > 0; t = P[t])     {
   if(flag[t] >= 0)         {
   if(flag[t])             {
                   dir[flag[t]] = d;                 tx[flag[t]] = x, ty[flag[t]] = y;             }             flag[t] = -1;         } else break;     } } void solve() {
   int i, j, k, t, x, y, dx, dy;     prepare(); for(x = 0; x < N; x ++)     {
           j = 0; for(y = 0; y < M; y ++)             deal(x, y, j, 6);     } for(x = 0; x < N; x ++)     {
           j = 0; for(y = M - 1; y >= 0; y --)             deal(x, y, j, 2);     } for(y = 0; y < M; y ++)     {
           j = 0; for(x = 0; x < N; x ++)             deal(x, y, j, 0);     } for(y = 0; y < M; y ++)     {
           j = 0; for(x = N - 1; x >= 0; x --)             deal(x, y, j, 4);     }     dx = 1, dy = 1; for(i = M - 1; i >= 0; i --)     {
           j = 0; for(x = 0, y = i; x < N && y < M; x += dx, y += dy)             deal(x, y, j, 7);     } for(i = 1; i < N; i ++)     {
           j = 0; for(x = i, y = 0; x < N && y < M; x += dx, y += dy)             deal(x, y, j, 7);     }     dx = -1, dy = -1; for(i = 0; i < M; i ++)     {
           j = 0; for(x = N - 1, y = i; x >= 0 && y >= 0; x += dx, y += dy)             deal(x, y, j, 3);     } for(i = N - 2; i >= 0; i --)     {
           j = 0; for(x = i, y = M - 1; x >= 0 && y >= 0; x += dx, y += dy)             deal(x, y, j, 3);     }     dx = 1, dy = -1; for(i = 0; i < M; i ++)     {
           j = 0; for(x = 0, y = i; x < N && y >= 0; x += dx, y += dy)             deal(x, y, j, 1);     } for(i = 1; i < N; i ++)     {
           j = 0; for(x = i, y = M - 1; x < N && y >= 0; x += dx, y += dy)             deal(x, y, j, 1);     }     dx = -1, dy = 1; for(i = 0; i < N; i ++)     {
           j = 0; for(x = i, y = 0; x >= 0 && y < M; x += dx, y += dy)             deal(x, y, j, 5);     } for(i = 1; i < M - 1; i ++)     {
           j = 0; for(x = N - 1, y = i; x >= 0 && y < M; x += dx, y += dy)             deal(x, y, j, 5);     } for(i = 1; i <= W; i ++)         printf("%d %d %c\n", tx[i], ty[i], dir[i] + 'A'); } int main() {
   while(scanf("%d%d%d", &N, &M, &W) == 3)     {
           init();         solve();     } return 0; }