题意：给出一个L*C的大写字母矩阵，再给出W个由大写字母组成的单词，求这些单词在矩阵中出现的位置及方向（0 < L <= 1000，0 < C <= 1000，0 < W <= 1000）。
题目链接：http://poj.org/problem?id=1204
——>>看到这题目，Sample好长啊～其实只是AC自动机，从边到边，枚举匹配。
#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int maxn = 1000 + 10;int L, C, W;
char G[maxn][maxn], w[maxn];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};struct Point{int l;int c;int d;
}ret[maxn];struct node{int id;int wlen;node *next[26];node *fail;node(){id = -1;wlen = -1;memset(next, 0, sizeof(next));fail = NULL;}
};struct AC{node *root;void init(){root = new node;}int idx(char c){return c - 'A';}void insert(char *s, int id){int len = strlen(s);node *p = root;for(int i = 0; i < len; i++){int c = idx(s[i]);if(!p->next[c]) p->next[c] = new node;p = p->next[c];}p->id = id;p->wlen = len;}void getFail(){root->fail = NULL;queue<node*> qu;qu.push(root);while(!qu.empty()){node *r = qu.front(); qu.pop();for(int c = 0; c < 26; c++) if(r->next[c]){node *u = r->next[c];qu.push(u);node *v = r->fail;while(v && !v->next[c]) v = v->fail;if(v) u->fail = v->next[c];else u->fail = root;}}}void find(int x, int y, char d){node *j = root;while(x >= 0 && x < L && y >= 0 && y < C){int c = idx(G[x][y]);while(j && !j->next[c]) j = j->fail;if(j) j = j->next[c];else j = root;node *p = j;while(p != root && p->id != -1){ret[p->id].l = x - dx[idx(d)] * (p->wlen - 1);ret[p->id].c = y - dy[idx(d)] * (p->wlen - 1);ret[p->id].d = d;p = p->fail;}x += dx[idx(d)];y += dy[idx(d)];}}
}ac;void read(){ac.init();for(int i = 0; i < L; i++){getchar();for(int j = 0; j < C; j++) G[i][j] = getchar();}for(int i = 0; i < W; i++){scanf("%s", w);ac.insert(w, i);}
}void solve(){ac.getFail();for(int i = 0; i < L; i++){ac.find(i, 0, 'B');ac.find(i, 0, 'C');ac.find(i, 0, 'D');ac.find(i, C-1, 'F');ac.find(i, C-1, 'G');ac.find(i, C-1, 'H');}for(int i = 0; i < C; i++){ac.find(0, i, 'D');ac.find(0, i, 'E');ac.find(0, i, 'F');ac.find(L-1, i, 'A');ac.find(L-1, i, 'B');ac.find(L-1, i, 'H');}for(int i = 0; i < W; i++) printf("%d %d %c\n", ret[i].l, ret[i].c, ret[i].d);
}int main()
{while(scanf("%d%d%d", &L, &C, &W) == 3){read();solve();}return 0;
}