刷的第二题AC自动机，这题简直了。。
用询问的串建AC自动机，然后。。。爆搜！
ACBB ACBB
ACCA A A
ABBC ——〉 A C
ACBA ACBA
像这样，将最外面的每一个点将有可能的方向走，比如第一行第一列的A向东南走，就可以得到一个ACBA的串，然后像模板题一样，去匹配找就行了。（老实讲我还是觉得这个很不靠谱。。谁叫人家地图小。。）
小细节，我将查询的字符串反着建ACM了，假设要找ACBA，那我就把它变成ABCA，有什么好处呢？就是找这个串时，我们从最下面的A一路往上，找到最上面的A，这样就可以直接找到起始点了。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int dx[8]={-1,-1,0,1,1,1,0,-1}; const int dy[8]={0,1,1,1,0,-1,-1,-1}; struct Trie { bool b; int s,w[30],fail; }tr[510000];int trlen; int a[1100000],len; void clean(int x) { tr[x].s=0;tr[x].b=false;tr[x].fail=0; memset(tr[x].w,0,sizeof(tr[x].w)); } void bt(int id) { int now=0; for(int i=1;i<=len;i++) { int x=a[i]; if(tr[now].w[x]==0) { tr[now].w[x]=++trlen; clean(trlen); } now=tr[now].w[x]; } tr[now].s=id; } int list[510000]; void bfs() { int head=1,tail=2;list[1]=0; while(head!=tail) { int now=list[head]; for(int x=1;x<=26;x++) { int son=tr[now].w[x]; if(son==0)continue; if(now==0)tr[son].fail=0; else { int p=tr[now].fail; while(p!=0&&tr[p].w[x]==0)p=tr[p].fail; tr[son].fail=max(tr[p].w[x],0); } list[tail]=son; tail++;if(tail==505000)tail=1; } head++;if(head==505000)head=1; } } int n,m,T; char mp[1100][1100],ss[1100]; struct Ans { int x,y,c; }ans[110000]; void Find(int x,int y,int i) { int now=0; while(x>=0&&y>=0&&x<n&&y<m) { int j=mp[x][y]-'A'+1; while(now!=0&&tr[now].w[j]==0)now=tr[now].fail; now=tr[now].w[j]; for(int k=now;k;k=tr[k].fail) { if(tr[k].b==false) { if(tr[k].s!=0) { ans[tr[k].s].x=x; ans[tr[k].s].y=y; ans[tr[k].s].c=(i+4)%8; } tr[k].b=1; } } x+=dx[i];y+=dy[i]; } } int main() { scanf("%d%d%d",&n,&m,&T); trlen=0;clean(0); for(int i=0;i<n;i++)scanf("%s",mp[i]); for(int i=1;i<=T;i++) { scanf("%s",ss+1);len=strlen(ss+1); for(int j=1;j<=len;j++)a[j]=ss[len-j+1]-'A'+1; bt(i); } bfs(); Find(0,0,2); Find(0,m-1,6); Find(n-1,0,2);Find(n-1,m-1,6); for(int j=0;j<m;j++) { Find(0,j,3);Find(0,j,4);Find(0,j,5); Find(n-1,j,0);Find(n-1,j,1);Find(n-1,j,7); } Find(0,0,4);Find(n-1,0,0); Find(0,m-1,4);Find(n-1,m-1,0); for(int i=0;i<n;i++) { Find(i,0,1);Find(i,0,2);Find(i,0,3); Find(i,m-1,5);Find(i,m-1,6);Find(i,m-1,7); } for(int i=1;i<=T;i++) printf("%d %d %c ",ans[i].x,ans[i].y,ans[i].c+'A'); return 0; }