POJ 1204Word Puzzles解题报告

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

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  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 }