/** 题目：pku1204 Word Puzzles 链接：http://poj.org/problem?id=1204 题意：给定一个L C(C <= 1000, L <= 1000)的字母矩阵， 再给定W(W <= 1000)个字符串，保证这些字符串都会在字母矩阵中出现(8种方向)， 求它们的出现位置和方向。 思路：将单词构成ac自动机，然后对矩阵字符串从8个方向跑ac自动机， 向下方向：所有的(0,i) (0<=i<sm)为起点，一直跑到最下面。 其他方向类推； 注意：由于在自动机上找到的位置是单词的末尾位置，要回溯单词长度去找起点位置。 为了方便，逆向插入单词构造自动机，那么当前找到结尾位置的(x,y)就是起点了。方向也是反向的。 本题还可以字典树做法： 单词构造字典树。 枚举每一个(i,j)从它往八个方向分别跑字典树。好的数据会时间卡掉。 AC自动机好文章：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html */ //#include<bits/stdc++.h> #include<cstring> #include<cstdio> #include<iostream> #include<algorithm> #include<queue> using namespace std; #define P pair<int,int> #define ms(x,y) memset(x,y,sizeof x) #define LL long long const int maxn = 1005; const int mod = 1e9+7; const int maxnode = maxn*maxn; const int sigma_size = 26; struct node { int x, y, dir; }ans[maxn]; int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}}; char s[maxn][maxn]; int sn, sm; struct AhoCorasickAutomata { int ch[maxnode][sigma_size]; int val[maxnode]; int sz; int f[maxnode]; int last[maxnode]; void clear(){sz = 1; memset(ch[0],0,sizeof ch[0]); } int idx(char c){return c-'A'; } void insert(char *s,int x) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++){ int c = idx(s[i]); if(!ch[u][c]){ memset(ch[sz], 0, sizeof ch[sz]); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = x; } void find(int x,int y,int f){ int j = 0; while(x>=0&&x<sn&&y>=0&&y<sm){ int c = idx(s[x][y]); j = ch[j][c]; if(val[j]) print(j,x,y,f); else if(last[j]) print(last[j],x,y,f); x = x+dir[f][0]; y = y+dir[f][1]; } } void print(int j,int x,int y,int dir) { if(j){ //cnt[val[j]]++; ans[val[j]].x = x, ans[val[j]].y = y; ans[val[j]].dir = dir; print(last[j],x,y,dir); } } void getFail(){ queue<int> q; f[0] = 0; for(int c = 0; c < sigma_size; c++){ int u = ch[0][c]; if(u){f[u] = 0; q.push(u); last[u] = 0;} } while(!q.empty()){ int r = q.front(); q.pop(); for(int c = 0; c < sigma_size; c++){ int u = ch[r][c]; if(!u){ ch[r][c] = ch[f[r]][c]; continue; }//if(!u) continue; q.push(u); int v = f[r]; while(v&&!ch[v][c]) v = f[v]; f[u] = ch[v][c]; last[u] = val[f[u]] ? f[u] : last[f[u]]; } } } } ac ; char t[maxn]; int main() { int w; while(scanf("%d%d%d",&sn,&sm,&w)!=EOF) { for(int i = 0; i < sn; i++) scanf("%s",s[i]); ac.clear(); for(int i = 1; i <= w; i++){ scanf("%s",t); reverse(t,t+strlen(t));///逆向插入，这样当查询的时候，当前的x，y就是起点。而不用回溯获取找起点。 ///同理，方向的最终结果也要反向再输出。 ac.insert(t,i); } ac.getFail(); for(int i = 0; i < sm; i++){ ac.find(0,i,4);///向下 ac.find(sn-1,i,0);///向上 ac.find(0,i,5);///向左下 ac.find(0,i,3);///向右下 ac.find(sn-1,i,1);///向右上 ac.find(sn-1,i,7);///向左上 } for(int i = 0; i < sn; i++){ ac.find(i,0,2);///向右 ac.find(i,sm-1,6);///向左 ac.find(i,0,3);///右下 ac.find(i,0,1);///右上 ac.find(i,sm-1,5);///左下 ac.find(i,sm-1,7);///左上 } for(int i = 1; i <= w; i++){ printf("%d %d %c ",ans[i].x,ans[i].y,(ans[i].dir+4)%8+'A'); } } return 0; } /* */