POJ1204 Word Puzzles AC自动机多串匹配

　　从字符矩阵的边缘字符扩展匹配分别记录最小值。
  1 //STATUS:C++_AC_704MS_12432KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 #include<set>
 14 using namespace std;
 15 //define
 16 #define pii pair<int,int>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define lson l,mid,rt<<1
 19 #define rson mid+1,r,rt<<1|1
 20 #define PI acos(-1.0)
 21 //typedef
 22 typedef __int64 LL;
 23 typedef unsigned __int64 ULL;
 24 //const
 25 const int N=1010;
 26 const int INF=0x3f3f3f3f;
 27 const int MOD=100000,STA=8000010;
 28 const LL LNF=1LL<<60;
 29 const double EPS=1e-8;
 30 const double OO=1e15;
 31 //Daily Use ...
 32 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
 33 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
 34 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 35 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 36 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 37 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
 38 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
 39 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
 40 //End
 41 
 42 int dx[8]={-1,-1,0,1,1,1,0,-1};
 43 int dy[8]={0,1,1,1,0,-1,-1,-1};
 44 char ma[]="ABCDEFGH";
 45 char s[N][N],temp[N];
 46 int ch[N*300][26];
 47 int val[N*300],f[N*300],last[N*300],ans[N][3],len[N];
 48 int sz,n,m,w;
 49 
 50 void init(){sz=1;mem(ch[0],0);}
 51 inline int idx(char c){return c-'A';}
 52 void insert(char *s,int v){
 53     int i,len=strlen(s),id,u=0;
 54     for(i=0;i<len;i++){
 55         id=idx(s[i]);
 56         if(!ch[u][id]){
 57             mem(ch[sz],0);
 58             val[sz]=0;
 59             ch[u][id]=sz++;
 60         }
 61         u=ch[u][id];
 62     }
 63     val[u]=v;
 64 }
 65 
 66 void getFail()
 67 {
 68     int u,c,r;
 69     queue<int> q;
 70     f[0]=0;
 71     for(c=0;c<26;c++){
 72         u=ch[0][c];
 73         if(u){f[u]=0;last[u]=0;q.push(u);}
 74     }
 75     while(!q.empty()){
 76         r=q.front();q.pop();
 77         for(c=0;c<26;c++){
 78             u=ch[r][c];
 79             if(!u){ch[r][c]=ch[f[r]][c];continue;}
 80             q.push(u);
 81             f[u]=ch[f[r]][c];
 82             last[u]=val[f[u]]?f[u]:last[f[u]];
 83         }
 84     }
 85 }
 86 
 87 void judge(int u,int x,int y,int dir)
 88 {
 89     if(u){
 90         int nx,ny,v=val[u];
 91         nx=x-dx[dir]*(len[v]-1);
 92         ny=y-dy[dir]*(len[v]-1);
 93         if(nx<ans[v][0] || ( nx==ans[v][0] && ny<ans[v][1] )
 94            || (nx==ans[v][0] && ny==ans[v][1] && dir<ans[v][2]) ){
 95             ans[v][0]=nx;
 96             ans[v][1]=ny;
 97             ans[v][2]=dir;
 98         }
 99         judge(last[u],x,y,dir);
100     }
101 }
102 
103 void find(int x,int y,int dir)
104 {
105     int c,u;
106     for(u=0;x>=0&&x<n && y>=0&&y<m;x+=dx[dir],y+=dy[dir]){
107         c=idx(s[x][y]);
108         u=ch[u][c];
109         if(val[u]){judge(u,x,y,dir);}
110         else if(last[u]){judge(last[u],x,y,dir);}
111     }
112 }
113 
114 void slove()
115 {
116     int i;
117     for(i=0;i<m;i++){
118         find(0,i,4);find(0,i,3);find(0,i,5);
119         find(n-1,i,0);find(n-1,i,7);find(n-1,i,1);
120     }
121 
122     for(i=0;i<n;i++){
123         find(i,0,2);find(i,0,1);find(i,0,3);
124         find(i,m-1,6);find(i,m-1,5);find(i,m-1,7);
125     }
126 }
127 
128 int main()
129 {
130  //   freopen("in.txt","r",stdin);
131     int i,j,k;
132     while(~scanf("%d%d%d",&n,&m,&w))
133     {
134         mem(ans,INF);
135         for(i=0;i<n;i++){
136             scanf("%s",s[i]);
137         }
138         init();
139         for(i=1;i<=w;i++){
140             scanf("%s",temp);
141             len[i]=strlen(temp);
142             insert(temp,i);
143         }
144         getFail();
145         slove();
146 
147         for(i=1;i<=w;i++){
148             printf("%d %d %c\n",ans[i][0],ans[i][1],ma[ans[i][2]]);
149         }
150     }
151     return 0;
152 }
POJ1204 Word Puzzles AC自动机 多串匹配

POJ1204 Word Puzzles AC自动机多串匹配
