tjh：

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int dx[8] = {-1,-1, 0, 1, 1, 1, 0,-1};
int dy[8] = { 0, 1, 1, 1, 0,-1,-1,-1};
//A表示正北，B表示东北，C表示正东，D表示东南，E表示正南，F表示西南，G表示正西，H表示西北
int L,C,W,id, ch[N*N][26],ed[N*N],pre[N*N];
char smap[N][N],str[N];
struct Ans{ int x,y,t;}ans[1005];
  
void ins(int x) {
    int p = 0,len =strlen(str);
    for(int i = len - 1;i > 0;--i) {
        int j= str[i] - 'A';
        if(!ch[p][j])ch[p][j] = ++id;
        p =ch[p][j];
    }
    ed[p] = x;
}
  
void build() {
    queue<int> q;for(int i = 0;i < 26;++i)if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()) {
        int x = q.front();q.pop();
        for(int i = 0;i < 26;++i) {
            int &y=ch[x][i];
            if(y==0)     y=ch[pre[x]][i];
            else    pre[y]=ch[pre[x]][i],q.push(y);
        }
    }
}
  
void query(int x,int y,int t) {
    int p= 0;
    while(x < L&&y < C&&x >= 0&&y >= 0) {
        p = ch[p][smap[x][y] - 'A'];
        //if(ed[p]) ans[ ed[p] ] ={ x,y,(t + 4)%8};
        int k=p;
        while(k){
            if(ed[k])if(ans[ed[k]].x == -1||ans[ed[k]].x > x||(ans[ed[k]].x == x && ans[ed[k]].y > y)||(ans[ed[k]].x == x && ans[ed[k]].y == y && (t+4)%8 < ans[ed[k]].t))ans[ ed[k] ].x=x,ans[ ed[k] ].y=y,ans[ ed[k] ].t=(t+4)%8;
            k = pre[k];
        }
        x += dx[t];y += dy[t];
    }
}
  
int main() {
    scanf("%d%d%d",&L,&C,&W);
    for(int i = 0;i < L;++i)scanf("%s",smap[i]);
    id=0;memset(ch,0,sizeof ch);for(int i = 1;i <= W;++i)scanf("%s",str),ins(i);
    memset(pre,0,sizeof pre);build();
    for(int i = 1;i <= W;++i)ans[i].x = -1; 
    for(int i = 0;i < L;++i)query(i,0,2),query(i,C - 1,6),query(i,0,1),query(i,0,3),query(i,C - 1,5),query(i,C - 1,7);
    for(int i = 0;i < C;++i)query(0,i,4),query(L - 1,i,0),query(0,i,3),query(0,i,5),query(L - 1,i,1),query(L - 1,i,7);
  
    for(int i = 1;i <= W;++i)printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].t + 'A');
    return 0;
}

tjh：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int dx[8] = {-1,-1, 0, 1, 1, 1, 0,-1};
int dy[8] = { 0, 1, 1, 1, 0,-1,-1,-1};
//A表示正北，B表示东北，C表示正东，D表示东南，E表示正南，F表示西南，G表示正西，H表示西北
int L,C,W,id, ch[N*N][26],ed[N*N],pre[N*N];
char smap[N][N],str[N];
struct Ans{ int x,y,t;}ans[1005];
  
void ins(int x)
{
    int p = 0,len =strlen(str);
    for(int i = len - 1;i >= 0;--i)
    {
        int j= str[i] - 'A';
        if(!ch[p][j])ch[p][j] = ++id;
        p =ch[p][j];
    }
    ed[p] = x;
}
  
void build()
{
    queue<int> q;for(int i = 0;i < 26;++i)if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty())
    {
        int x = q.front();q.pop();
        for(int i = 0;i < 26;++i)
        {
            int &y=ch[x][i];
            if(y==0)     y=ch[pre[x]][i];
            else    pre[y]=ch[pre[x]][i],q.push(y);
        }
    }
}
  
void query(int x,int y,int t)
{
    int p= 0;
    while(x < L&&y < C&&x >= 0&&y >= 0)
    {
        p = ch[p][smap[x][y] - 'A'];
        //if(ed[p]) ans[ ed[p] ] ={ x,y,(t + 4)%8};
        int k=p;
        while(k){
	        if(ed[k])if(ans[ed[k]].x == -1||ans[ed[k]].x > x||(ans[ed[k]].x == x && ans[ed[k]].y > y)||(ans[ed[k]].x == x && ans[ed[k]].y == y && (t+4)%8 < ans[ed[k]].t))ans[ ed[k] ].x=x,ans[ ed[k] ].y=y,ans[ ed[k] ].t=(t+4)%8;
	        	k = pre[k];
			}
        x += dx[t];y += dy[t];
    }
}
  
int main()
{
    scanf("%d%d%d",&L,&C,&W);
    for(int i = 0;i < L;++i)scanf("%s",smap[i]);
    id=0;memset(ch,0,sizeof ch);for(int i = 1;i <= W;++i)scanf("%s",str),ins(i);
    memset(pre,0,sizeof pre);build();
    for(int i = 1;i <= W;++i)ans[i].x = -1; 
    for(int i = 0;i < L;++i)query(i,0,2),query(i,C - 1,6),query(i,0,1),query(i,0,3),query(i,C - 1,5),query(i,C - 1,7);
    for(int i = 0;i < C;++i)query(0,i,4),query(L - 1,i,0),query(0,i,3),query(0,i,5),query(L - 1,i,1),query(L - 1,i,7);
  
    for(int i = 1;i <= W;++i)printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].t + 'A');
      
    return 0;
}