AC自动机+搜索，直接trie也能过
#include <stdio.h>
#include <string.h>
char str[1010][1010], temstr[1010];
int r, c, n, point;
int queue[501000];
int div[8][2]={{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
struct P
{
int child[27];
int len, fail, id, num;
}node[501000];
struct ANS
{
int x, y;
char c;
}ans[1010];
void insert(int id)
{
int p = 0, len= strlen(temstr), t;
for ( int i = 0 ; temstr[i] ; i++ )
{
t= temstr[i]-'A';
if ( !node[p].child[t] )
node[p].child[t]= point++;
p= node[p].child[t];
}
node[p].num++;
node[p].id=id;
node[p].len=len;
}
void init()
{
memset(node, 0, sizeof(node));
point= 1;
}
void buildAC()
{
int rear=-1, front=0, i, k;
queue[0]= 0;
node[0].fail= -1;
while ( rear < front )
{
int now= queue[++rear];
for ( i = 0 ; i < 26 ; i++ )
{
int t= node[now].child[i];
if ( !t ) continue;
for ( k = node[now].fail ; k != -1 ; k= node[k].fail )
if (node[k].child[i])
{
node[t].fail=node[k].child[i];
break;
}
if ( k == -1 )
node[t].fail=0;
queue[++front]= t;
}
}
}
void find(int x, int y, int k)
{
int i = x, j= y, p= 0;
while ( 0 <= i && i < r && 0 <= j && j < c )
{
int ch= str[i][j]-'A';
if (node[p].child[ch])
{
p= node[p].child[ch];
if ( node[p].num>0 )
{
int id= node[p].id;
ans[id].x= i-(node[p].len-1)*div[k][0];
ans[id].y= j-(node[p].len-1)*div[k][1];
ans[id].c= k+'A';
node[p].num= 0;
}
i+=div[k][0];
j+=div[k][1];
}
else if(p)
{
p= node[p].fail;
if (node[p].num>0)
{
int id= node[p].id;
ans[id].x= i-(node[p].len-1)*div[k][0];
ans[id].y= j-(node[p].len-1)*div[k][1];
ans[id].c= k+'A';
node[p].num= 0;
}
}
else
{
i+=div[k][0];
j+=div[k][1];
}
}
}
void get()
{
int i;
for ( i = 0 ; i < c ; i++ )
{
find(r-1, i, 7);
find(r-1, i, 0);
find(r-1, i, 1);
find(0, i, 3);
find(0, i, 4);
find(0, i, 5);
}
for ( i = 0 ; i < r ; i++ )
{
find(i, 0, 1);
find(i, 0, 2);
find(i, 0, 3);
find(i, c-1, 5);
find(i, c-1, 6);
find(i, c-1, 7);
}
}
int main()
{
scanf("%d%d%d", &r, &c, &n);
int i;
init();
for ( i = 0 ; i < r ; i++ )
scanf("%s", str[i]);
for ( i = 0 ; i < n ; i++ )
{
scanf("%s", temstr);
insert(i+1);
}
buildAC();
get();
for ( int i = 0 ; i < n ; i++ )
printf("%d %d %c\n", ans[i+1].x, ans[i+1].y, ans[i+1].c);
return 0;
}