rt

用的广义 SAM，样例可过不知道为啥 T 了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define N 1505

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,char Extra=0) {
    if (x<0) putchar('-'),x=-x; if (x>9) W(x/10);
    putchar(x%10+'0'); if (Extra) putchar(Extra);
}

using namespace std;
int n,m,k,vis[N]; char mp[N][N]; string s[N];
struct Ans { int x,y; char ch; }ans[N];
const int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
vector<pair<int,int> > Pos[N];

int tot=1,np=1,ch[N*N][26],fail[N*N],len[N*N]; pair<int,int> pos[N*N];

void ins(int c,int i,int j) {
    int p=np; len[np=++tot]=len[p]+1,pos[np]=make_pair(i,j);
    while (p and !ch[p][c]) ch[p][c]=np,p=fail[p];
    if (!p) fail[np]=1;
    else {
        int q=ch[p][c];
        if (len[q]==len[p]+1) fail[np]=q;
        else {
            int nq=++tot;
            len[nq]=len[p]+1,pos[nq]=pos[q];
            fail[nq]=fail[q],fail[q]=fail[np]=nq;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            while (p and ch[p][c]==q) ch[p][c]=nq,p=fail[p];
        }
    }
}

void init() {
    memset(ch,0,(tot+1)*sizeof(ch[0]));
    memset(fail,0,(tot+1)*sizeof(int));
    memset(len,0,(tot+1)*sizeof(int));
    for (int i=1;i<=tot;i++) pos[i]={0,0};
    tot=np=1;
}

int main() {
    int T=R();
    while (T--) {
        n=R(),m=R(),k=R();
        for (int i=0;i<n;i++) cin>>mp[i];
        for (int i=1;i<=k;i++) cin>>s[i],vis[i]=0;
        for (int i=0;i<8;i++) Pos[i].clear();
        for (int i=0;i<m;i++) Pos[3].emplace_back(0,i),Pos[4].emplace_back(0,i),Pos[5].emplace_back(0,i);
        for (int i=0;i<m;i++) Pos[7].emplace_back(n-1,i),Pos[0].emplace_back(n-1,i),Pos[1].emplace_back(n-1,i);
        for (int i=0;i<n;i++) Pos[1].emplace_back(i,0),Pos[2].emplace_back(i,0),Pos[3].emplace_back(i,0);
        for (int i=0;i<n;i++) Pos[5].emplace_back(i,m-1),Pos[6].emplace_back(i,m-1),Pos[7].emplace_back(i,m-1);
        for (int i=0;i<8;i++) {
            init();
            for (auto [x,y]:Pos[i]) {
                np=1;
                while (x>=0 and x<n and y>=0 and y<m) 
                    ins(mp[x][y]-'A',x,y),x+=dx[i],y+=dy[i];
            }
            for (int j=1;j<=m;j++) if (!vis[j]) {
                int p=1; bool flag=0;
                for (auto c:s[j]) {
                    if (!ch[p][c-'A']) { flag=1; break; }
                    p=ch[p][c-'A'];
                }
                if (!flag) vis[j]=1,ans[j]={(int)(pos[p].first-(s[j].size()-1)*dx[i]),(int)(pos[p].second-(s[j].size()-1)*dy[i]),(char)(i+'A')};
            }
        }
        for (int i=1;i<=k;i++) printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].ch);
        if (T) printf("\n");
    }
    return 0;
}