确实是一道字符串好题，用AC自动机做的，不过思路比较简单，并且AC自动机还要加一些优化，要找的是串是否出现在了模式串中，这样有很多位置不用去比较，比如说，要考虑一行的时候，这一行的子串就不用再次验证了，因为出现在了这一行的一部分中一定会出现在整个这一行中的，这样能减少处理时间

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 #define N 1005  6 struct node  7 {  8     bool istail;  9     node *next[26],*fail; 10     int id; 11 }qq[100005],*que[100005]; 12 node *rt = new node(); 13 char key[N]; 14 int len[N]; 15 int dix[8][2] = {-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1}; 16 char res[9] = {
    "ABCDEFGH"}; 17 struct pos 18 { 19     int x,y,dis; 20 }; 21 pos ans[N]; 22 char mes[N][N]; 23 int k; 24 void insert(char *str,int id) 25 { 26     int i; 27     int temp; 28     node *p = rt; 29     for(i = 0;str[i]; i++) 30     { 31         temp = str[i] - 'A'; 32         if(p->next[temp] == NULL) 33         { 34             qq[k].istail = false; 35             qq[k].fail = NULL; 36             memset(qq[k].next,NULL,sizeof(qq[k].next)); 37             p->next[temp] = &qq[k++]; 38         } 39         p = p->next[temp]; 40     } 41     p->istail = true; 42     p->id = id; 43 } 44 void ac() 45 { 46     int f = 0,r = 0; 47     int i; 48     node *p,*temp; 49     rt->fail = NULL; 50     que[r++] = rt; 51     while(f < r) 52     { 53         temp = que[f++]; 54         for(i = 0;i < 26;i++) 55         { 56             if(temp->next[i] == NULL) 57                 continue; 58             if(temp == rt) 59                 temp->next[i]->fail = rt; 60             else 61             { 62                 for(p = temp->fail; p != NULL; p = p->fail) 63                 { 64                     if(p->next[i] != NULL) 65                     { 66                         temp->next[i]->fail = p->next[i]; 67                         break; 68                     } 69                 } 70                 if(p == NULL) 71                 { 72                     temp->next[i]->fail = rt; 73                 } 74             } 75             que[r++] = temp->next[i]; 76         } 77     } 78 } 79 void query(int x,int y,int i) 80 { 81     int tem; 82     int nx = x,ny = y; 83     node *p,*q; 84     p = rt; 85     for(;mes[x][y];x += dix[i][0],y += dix[i][1]) 86     { 87         tem = mes[x][y] - 'A'; 88         while(p->next[tem] == NULL &&p != rt) 89             p = p->fail; 90         p = p->next[tem]; 91         if(p == NULL) 92             p = rt; 93         q = p; 94         while(q != rt) 95         { 96             if(q->istail) 97             { 98                 q->istail = false; 99                 ans[q->id].x = x - dix[i][0] * (len[q->id] - 1) - 1;100                 ans[q->id].y = y - dix[i][1] * (len[q->id] - 1) - 1;101                 ans[q->id].dis = i;102             }103             q = q->fail;104         }105     }106 }107 int main()108 {109     int r,c,m;110     int i,j;111     for(i = 0;i < 26; i++)112         rt->next[i] = NULL;113     memset(mes,0,sizeof(mes));114     scanf("%d%d%d",&r,&c,&m);115     for(i = 1;i <= r; i++)116         scanf("%s",mes[i]+1);117     for(i = 0;i < m;i++)118     {119         scanf("%s",key);120         len[i] = strlen(key);121         insert(key,i);122     }123     ac();124     for(i = 1;i <= r; i++)125     {126         query(i,1,1),query(i,1,2),query(i,1,3);127         query(i,c,5),query(i,c,6),query(i,c,7);128     }129     for(i = 1;i <= c; i++)130     {131         query(1,i,3),query(1,i,4),query(1,i,5);132         query(r,i,1),query(r,i,0),query(r,i,7);133     }134     for(i = 0;i < m;i++)135         printf("%d %d %c\n",ans[i].x,ans[i].y,res[ans[i].dis]);136     return 0;137 }