我们对模式串建立AC自动机，然后就比较板子了，只需要把\(8\)个方向都跑一遍匹配就可以了。
时间复杂度是\(O(T\times 8nm)\)。
注意输入是大写字母。
点击查看代码
#include<bits/stdc++.h>
#define K 1010//模式串个数 & 矩阵长宽
#define N 1000010//节点个数（模式串总长）
#define C 26//字符集大小
using namespace std;
int tt,n,m,k;
int cnt,tr[N][C],fail[N],en[N],len[N];
int q[N],head,tail;
int ansx[K],ansy[K],ansd[K];
int dx[8]{-1,-1,0,1,1,1,0,-1},dy[8]{0,1,1,1,0,-1,-1,-1};
string s[K],t;
void clear(int x){
memset(tr[x],0,sizeof tr[x]);
fail[x]=en[x]=len[x]=0;
}
void ins(string s,int num){
int p=0;
for(char i:s){
int c=i-'A';
if(!tr[p][c]) tr[p][c]=++cnt,clear(cnt);
p=tr[p][c];
}
en[p]=num,len[p]=s.size();
}
void get_fail(){
head=0,tail=-1;
for(int i=0;i<26;i++) if(tr[0][i]) q[++tail]=tr[0][i];
while(head<=tail){
int u=q[head++];
for(int i=0;i<26;i++){
if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q[++tail]=tr[u][i];
else tr[u][i]=tr[fail[u]][i];
}
}
}
void query(int x,int y,int d){
int p=0;
while(x<n&&y<m&&x>=0&&y>=0){
p=tr[p][s[x][y]-'A'];
int xx=x-dx[d]*(len[p]-1),yy=y-dy[d]*(len[p]-1);//开始位置
if(en[p]&&(xx<ansx[en[p]]||(xx==ansx[en[p]]&&yy<ansy[en[p]])))
ansx[en[p]]=xx,ansy[en[p]]=yy,ansd[en[p]]=d;
x+=dx[d],y+=dy[d];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>tt;
while(tt--){
memset(ansx,127,sizeof ansx);
memset(ansy,127,sizeof ansy);
clear(0);
cin>>n>>m>>k;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=1;i<=k;i++){
cin>>t;
ins(t,i);
}
get_fail();
for(int i=0;i<n;i++) for(int j=0;j<8;j++) query(i,0,j),query(i,m-1,j);
for(int i=0;i<n;i++) for(int j=0;j<8;j++) query(0,i,j),query(n-1,i,j);
for(int i=1;i<=k;i++)
cout<<ansx[i]<<" "<<ansy[i]<<" "<<char(ansd[i]+'A')<<"\n";
cout<<"\n";
}
return 0;
}
上面的写法是每匹配成功，就计算得到字符串的开始位置。
还有一种写法，就是反向建Trie，把模式串全部翻转再扔进去。这样匹配成功的位置直接就是字符串的开始位置了，效率会高不少（370ms => 200ms）。需要注意这样写的话，匹配成功时的方向和实际方向是相反的，需要反向一下。
点击查看代码
#include<bits/stdc++.h>
#define K 1010//模式串个数 & 矩阵长宽
#define N 1000010//节点个数（模式串总长）
#define C 26//字符集大小
using namespace std;
int tt,n,m,k;
int cnt,tr[N][C],fail[N],en[N];
int q[N],head,tail;
int ansx[K],ansy[K],ansd[K];
int dx[8]{-1,-1,0,1,1,1,0,-1},dy[8]{0,1,1,1,0,-1,-1,-1};
string s[K],t;
void clear(int x){
memset(tr[x],0,sizeof tr[x]);
fail[x]=en[x]=0;
}
void ins(string s,int num){
int p=0,n=s.size();
for(int i=n-1;i>=0;i--){
int c=s[i]-'A';
if(!tr[p][c]) tr[p][c]=++cnt,clear(cnt);
p=tr[p][c];
}
en[p]=num;
}
void get_fail(){
head=0,tail=-1;
for(int i=0;i<26;i++) if(tr[0][i]) q[++tail]=tr[0][i];
while(head<=tail){
int u=q[head++];
for(int i=0;i<26;i++){
if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q[++tail]=tr[u][i];
else tr[u][i]=tr[fail[u]][i];
}
}
}
void query(int x,int y,int d){
int p=0;
while(x<n&&y<m&&x>=0&&y>=0){
p=tr[p][s[x][y]-'A'];
if(en[p]&&(x<ansx[en[p]]||(x==ansx[en[p]]&&y<ansy[en[p]])))
ansx[en[p]]=x,ansy[en[p]]=y,ansd[en[p]]=(d+4)%8;//+4是因为Trie是倒着建的
x+=dx[d],y+=dy[d];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>tt;
while(tt--){
memset(ansx,127,sizeof ansx);
memset(ansy,127,sizeof ansy);
clear(0);
cin>>n>>m>>k;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=1;i<=k;i++){
cin>>t;
ins(t,i);
}
get_fail();
for(int i=0;i<n;i++) for(int j=0;j<8;j++) query(i,0,j),query(i,m-1,j);
for(int i=0;i<n;i++) for(int j=0;j<8;j++) query(0,i,j),query(n-1,i,j);
for(int i=1;i<=k;i++)
cout<<ansx[i]<<" "<<ansy[i]<<" "<<char(ansd[i]+'A')<<"\n";
cout<<"\n";
}
return 0;
}