给一个L*C字符矩阵和W个字符串，问那些字符串出现在矩阵的位置，横竖斜八个向。
就是个多模式匹配的问题，直接AC自动机搞了，枚举字符矩阵八个方向的所有字符串构成主串，然后在W个模式串构造的AC自动机上跑。
另外，temp指针的那个找遗漏后缀的过程执行时标记一下，下一次再到这个结点就不需要再进行一次temp的过程，这样的时间复杂度就是O(W个模式串总长+LC)。
一开始还想8个方向分别计算坐标= =写第二个方向懒得写了，然后就忽然想到可以一开始构造主串时就存坐标。。最后代码很是挺长的。。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 111111
int tn,ch[MAXN][],flag[MAXN],fail[MAXN],len[MAXN];
void insert(char *s,int k,int l){
int x=;
for(int i=; s[i]; ++i){
int y=s[i]-'A';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
flag[x]=k;
len[x]=l;
}
void getFail(){
memset(fail,,sizeof(fail));
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=; i<; ++i){
if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i];
else ch[x][i]=ch[fail[x]][i];
}
}
} int n,m;
int ansx[],ansy[],anso[];
char str[]; int sx[],sy[];
void match(char o){
int x=;
for(int i=; str[i]; ++i){
int y=str[i]-'A';
x=ch[x][y];
int tmp=x;
while(flag[tmp] && tmp){
if(flag[tmp]>){
int &idx=flag[tmp];
ansx[idx]=sx[i-len[tmp]+];
ansy[idx]=sy[i-len[tmp]+];
anso[idx]=o;
idx=-;
}else if(flag[tmp]==-) break;
tmp=fail[tmp];
}
}
}
char map[][];
int main(){
int w;
scanf("%d%d%d",&n,&m,&w);
for(int i=; i<n; ++i) scanf("%s",map[i]);
for(int i=; i<=w; ++i){
scanf("%s",str);
insert(str,i,strlen(str));
}
getFail();
int sn;
//zero
for(int i=; i<m; ++i){
for(int j=; j<n; ++j){
sx[n-j-]=j; sy[n-j-]=i;
str[n-j-]=map[j][i];
}
str[n]=;
match('A');
}
//one
for(int i=; i<n; ++i){
int x=i,y=,sn=;
while(x>= && y<m){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
--x; ++y;
}
str[sn]=;
match('B');
}
for(int i=; i<m; ++i){
int x=n-,y=i,sn=;
while(x>= && y<m){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
--x; ++y;
}
str[sn]=;
match('B');
}
//two
for(int i=; i<n; ++i){
for(int j=; j<m; ++j){
sx[j]=i; sy[j]=j;
str[j]=map[i][j];
}
str[m]=;
match('C');
}
//three
for(int i=; i<m; ++i){
int x=,y=i,sn=;
while(x<n && y<m){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
++x; ++y;
}
str[sn]=;
match('D');
}
for(int i=; i<n; ++i){
int x=i,y=,sn=;
while(x<n && y<m){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
++x; ++y;
}
str[sn]=;
match('D');
}
//four
for(int i=; i<m; ++i){
for(int j=; j<n; ++j){
sx[j]=j; sy[j]=i;
str[j]=map[j][i];
}
str[n]=;
match('E');
}
//five
for(int i=; i<m; ++i){
int x=,y=i,sn=;
while(x<n && y>=){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
++x; --y;
}
str[sn]=;
match('F');
}
for(int i=; i<n; ++i){
int x=i,y=m-,sn=;
while(x<n && y>=){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
++x; --y;
}
str[sn]=;
match('F');
}
//six
for(int i=; i<n; ++i){
for(int j=; j<m; ++j){
sx[m-j-]=i; sy[m-j-]=j;
str[m-j-]=map[i][j];
}
str[m]=;
match('G');
}
//seven
for(int i=; i<m; ++i){
int x=n-,y=i,sn=;
while(x>= && y>=){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
--x; --y;
}
str[sn]=;
match('H');
}
for(int i=; i<n-; ++i){
int x=i,y=m-,sn=;
while(x>= && y>=){
sx[sn]=x; sy[sn]=y;
str[sn++]=map[x][y];
--x; --y;
}
str[sn]=;
match('H');
}
for(int i=; i<=w; ++i){
printf("%d %d %c\n",ansx[i],ansy[i],anso[i]);
}
return ;
}