解题报告（6）——Word puzzles

#include
#include
#include
#include
#include
#includeusing namespace std;const int dx[9]={0,-1,-1, 0, 1, 1, 1, 0,-1};
const int dy[9]={0, 0, 1, 1, 1, 0,-1,-1,-1};
/*dx,dy:指向八个方向的表*/ 
int n,m,q,tot,cnt,head,tail;
/*tot:记录当前询问; cnt:记录当前的动态分配节点*/ 
char s[1010][1010];
/*s:字符分配地图*/
int f[1100000][27],first[1100000],lent[1100000];
/*f:AC自动机; first:记录是否为结束节点即编号; lent:和first对应，当前的长度*/ 
int fail[1100000],queue[11000000];
/*fail:AC自动机fail指针; queue:AC自动机的广搜队列*/
string ss;struct data /*离线：输出记录*/ 
{int x;int y;char dir;
}out[1010];void build(string &s) /*字典树的建立*/
{int position=0;for(int i=0;i>n>>m>>q;for(int i=0;i>s[i];}for(int i=1;i<=q;++i){cin>>ss;build(ss);}
}void build_AC(void)  /*构建AC自动机*/ 
{head=0;tail=1;queue[1]=0;while(head<tail)  /*广搜*/ {head++;for(int i=0;i<26 i="" fail="" if="" f="" queue="" head="" i="" if="" queue="" head="" fail="" f="" queue="" head="" i="" f="" fail="" queue="" head="" i="" tail="" queue="" tail="" f="" queue="" head="" i="" else="" f="" queue="" head="" i="" f="" fail="" queue="" head="" i="" void="" find="" int="" l="" int="" r="" int="" type="" int="" position="0;" while="" l="">=0&&l=0&&r<m) /*越界判断*/ {position=f[position][s[l][r]-'A'];l+=dx[type];   r+=dy[type];  /*保证方向不变，直线处理*/ if(first[position]&&out[first[position]].x<0)/*处理匹配上的字符串信息*/ {int v=first[position];out[v].x=l-lent[position]*dx[type];out[v].y=r-lent[position]*dy[type];out[v].dir=type+'A'-1;}}
}void get(void) /*跑AC匹配*/ 
{for(int k=1;k<=8;++k){for(int i=0;i<n;++i){find(i,0,k);find(i,m-1,k);}for(int i=0;i<m;++i){find(0,i,k);find(n-1,i,k);}}for(int i=1;i<=q;++i){cout<<out[i].x<<" "<<out[i].y<<" "<<out[i].dir<<'\n';}
}int main(void)
{ios::sync_with_stdio(false);cin.tie(NULL);  /*解绑*/ memset(out,-1,sizeof(out)); /*初始化*/read();build_AC();get();return 0;
}