poj 1204

大意：给出一个棋盘puzzle，，和w个模式串，，在棋盘中寻找模式串。。棋盘中任意一格有8个方向可以走。。

解题思路： AC自动机 + 枚举8个方向即可

get_trie(),get_ac().直接用模版。。。。

query 有一点小技巧。。需要枚举8个方向，，对于一行，我们对竖直方向上的枚举可以省略，因为我们在竖直方向上枚举时，会补充上。。

另外我们无需枚举一行中的每一个点，，只需第一个即可，因为，，我们在一个方向上枚举时，，会包含到后面的。

  1 #include <iostream>
  2 #include<cstring>
  3 using namespace std;
  4 struct point{
  5     point *fail;
  6     point *next[26];
  7     bool istail;//是否为单词结尾
  8     int id;//单词的输入顺序
  9     point(){   //初始化
 10         istail =false;
 11         fail = NULL;
 12         memset(next,NULL,sizeof(next));
 13     }
 14 }*q[5000005];//bfs 获得fail 用
 15 
 16 struct pos{
 17     int x,y,dis;
 18 };
 19 pos ans[1005];
 20 point *root = NULL;
 21 int l,c,w;
 22 char map[1005][1005];//puzzle
 23 char str[1005];//模版串
 24 int len[1005];//记录每个摸版的长度
 25 int tail,head;
 26 int dix[8][2] = {-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};//顺时针，，上下左右。。。八个方向
 27 char res[9]={"ABCDEFGH"};
 28 void build_trie(char *str,int id){
 29     point *p = root;
 30     int i=0,index;
 31     while(str[i]){
 32         index = str[i]-'A';
 33         if(p->next[index]==NULL) p->next[index] = new point();
 34         p = p->next[index];
 35         i++;
 36     }
 37     p->istail = true;
 38     p->id = id;
 39 }
 40 void get_ac(){
 41     int i;
 42     root->fail = NULL;
 43     q[head++] = root;
 44     while(head!=tail){
 45         point *temp = q[tail++];
 46         point *p =NULL;
 47         for(i=0;i<26;i++){
 48             if(temp->next[i]!=NULL){
 49                 if(temp==root) temp->next[i]->fail=root;
 50                 else{
 51                     p = temp->fail;
 52                     while(p!=NULL){
 53                         if(p->next[i]!=NULL){
 54                             temp->next[i]->fail = p->next[i];
 55                             break;
 56                         }
 57                         p = p->fail;
 58                     }
 59                     if(p==NULL) temp->next[i]->fail = root;
 60                 }
 61                 q[head++] = temp->next[i];
 62             }
 63         }
 64     }
 65 }
 66 
 67 void query(int x,int y,int i){
 68     int index;
 69     point *p,*qq;
 70     p = root;
 71     for(;map[x][y];x+=dix[i][0],y+=dix[i][1]){
 72         index = map[x][y]-'A';
 73         while(p->next[index]==NULL&&p!=root) p = p->fail;
 74         p = p->next[index];
 75         if(p==NULL)
 76             p = root;
 77         qq= p;
 78         while(qq!=root){
 79             if(qq->istail){
 80                 qq->istail = false;
 81                 ans[qq->id].x = x-dix[i][0]*(len[qq->id]-1)-1;//从1开始记得数
 82                 ans[qq->id].y = y-dix[i][1]*(len[qq->id]-1);
 83                 ans[qq->id].dis = i;
 84             }
 85             qq = qq->fail;
 86         }
 87     }
 88 }
 89 int main()
 90 {
 91     root = new point();
 92     cin>>l>>c>>w;
 93     for(int i=1;i<=l;i++)
 94         cin>>map[i];
 95     for(int i=0;i<w;i++){
 96         cin>>str;
 97         len[i] = strlen(str);
 98         build_trie(str,i);
 99     }
100     head = tail =0;
101     get_ac();
102     for(int i=1;i<=l;i++){//枚举水平
103         query(i,0,1),query(i,0,2),query(i,0,3);//一行只需枚举开头和结尾即可,一列同样
104         query(i,c-1,5),query(i,c-1,6),query(i,c-1,7);
105     }
106     for(int i=0;i<c;i++){//枚举竖直
107         query(1,i,3),query(1,i,4),query(1,i,5);
108         query(l,i,7),query(l,i,0),query(l,i,1);
109     }
110 
111     for(int i=0;i<w;i++){
112         cout<<ans[i].x<<" "<<ans[i].y<<" "<<res[ans[i].dis]<<endl;
113     }
114     return 0;
115 }