【poj1226-出现或反转后出现在每个串的最长公共子串】后缀数组
题意：求n个串的最长公共子串，子串出现在一个串中可以是它的反转串出现。总长<=10^4.
题解：
对于每个串，把反转串也连进去。
二分长度，分组，判断每个组。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=2*21000; 8 int n,sl,cl,c[N],rk[N],sa[N],Rs[N],wr[N],y[N],h[N],st[N],ed[N],fst[N],fed[N]; 9 char s[N]; 10 bool vis[N]; 11 12 void get_sa(int m) 13 { 14 for(int i=1;i<=cl;i++) rk[i]=c[i]; 15 for(int i=1;i<=m;i++) Rs[i]=0; 16 for(int i=1;i<=cl;i++) Rs[rk[i]]++; 17 for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; 18 for(int i=cl;i>=1;i--) sa[Rs[rk[i]]--]=i; 19 20 int ln=1,p=0; 21 while(p<cl) 22 { 23 int k=0; 24 for(int i=cl-ln+1;i<=cl;i++) y[++k]=i; 25 for(int i=1;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln; 26 27 for(int i=1;i<=cl;i++) wr[i]=rk[y[i]]; 28 for(int i=1;i<=m;i++) Rs[i]=0; 29 for(int i=1;i<=cl;i++) Rs[wr[i]]++; 30 for(int i=1;i<=m;i++) Rs[i]+=Rs[i-1]; 31 for(int i=cl;i>=1;i--) sa[Rs[wr[i]]--]=y[i]; 32 33 for(int i=1;i<=cl;i++) wr[i]=rk[i]; 34 for(int i=cl+1;i<=cl+ln;i++) wr[i]=0; 35 p=1;rk[sa[1]]=1; 36 for(int i=2;i<=cl;i++) 37 { 38 if(wr[sa[i]]!=wr[sa[i-1]] || wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++; 39 rk[sa[i]]=p; 40 } 41 ln*=2,m=p; 42 } 43 sa[0]=0,rk[0]=0; 44 } 45 46 void get_h() 47 { 48 int k=0,j; 49 for(int i=1;i<=cl;i++) if(rk[i]!=1) 50 { 51 j=sa[rk[i]-1]; 52 if(k) k--; 53 while(c[i+k]==c[j+k] && i+k<=cl && j+k<=cl) k++; 54 h[rk[i]]=k; 55 } 56 h[0]=0; 57 } 58 59 int idx(int x) 60 { 61 for(int i=1;i<=n;i++) 62 if((st[i]<=x && x<=ed[i]) || (fst[i]<=x && x<=fed[i])) return i; 63 } 64 65 bool check(int k) 66 { 67 memset(vis,0,sizeof(vis)); 68 for(int i=1;i<=cl;i++) 69 { 70 if(h[i]<k) 71 { 72 int cnt=0; 73 for(int j=1;j<=n;j++) if(vis[j]) cnt++; 74 if(cnt==n) return 1; 75 memset(vis,0,sizeof(vis)); 76 } 77 vis[idx(sa[i])]++; 78 } 79 int cnt=0; 80 for(int j=1;j<=n;j++) if(vis[j]) cnt++; 81 if(cnt==n) return 1; 82 return 0; 83 } 84 85 int main() 86 { 87 freopen("a.in","r",stdin); 88 int T; 89 scanf("%d",&T); 90 while(T--) 91 { 92 scanf("%d",&n); 93 int num=123; 94 cl=0; 95 for(int i=1;i<=n;i++) 96 { 97 scanf("%s",s+1); 98 sl=strlen(s+1); 99 if(i>1) c[++cl]=++num; 100 st[i]=cl+1;for(int j=1;j<=sl;j++) c[++cl]=s[j];ed[i]=cl; 101 c[++cl]=++num; 102 fst[i]=cl+1;for(int j=sl;j>=1;j--) c[++cl]=s[j];fed[i]=cl; 103 } 104 if(n==1) {printf("%d ",sl);continue;} 105 get_sa(300); 106 get_h(); 107 // for(int i=1;i<=cl;i++) printf("%c",c[i]);printf(" "); 108 // for(int i=1;i<=cl;i++) printf("%d ",c[i]);printf(" "); 109 // for(int i=1;i<=cl;i++) printf("%d ",sa[i]);printf(" "); 110 // for(int i=1;i<=cl;i++) printf("%d ",rk[i]);printf(" "); 111 // for(int i=1;i<=cl;i++) printf("%d ",h[i]);printf(" "); 112 int l=0,r=cl,mid; 113 while(l<r) 114 { 115 mid=(l+r+1)/2; 116 if(check(mid)) l=mid; 117 else r=mid-1; 118 } 119 printf("%d ",l); 120 } 121 return 0; 122 }
这一题我曾经用kmp暴力水过。。贴一下代码
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 9 const int N=110,Inf=(int)1e9; 10 char s[N][N],c1[N],c2[N]; 11 int n,id,cl,l[N],nt[N],nxt[N]; 12 13 void kmp_nt() 14 { 15 nt[1]=0; 16 for(int i=2,p=0;i<=cl;i++) 17 { 18 while(c1[p+1]!=c1[i] && p) p=nt[p]; 19 if(c1[p+1]==c1[i]) p++; 20 nt[i]=p; 21 } 22 23 nxt[1]=0; 24 for(int i=2,p=0;i<=cl;i++) 25 { 26 while(c2[p+1]!=c2[i] && p) p=nxt[p]; 27 if(c2[p+1]==c2[i]) p++; 28 nxt[i]=p; 29 } 30 } 31 32 bool kmp_td(int x) 33 { 34 for(int i=1,p=0;i<=l[x];i++) 35 { 36 while(c1[p+1]!=s[x][i] && p) p=nt[p]; 37 if(c1[p+1]==s[x][i]) p++; 38 if(p==cl) return 1; 39 } 40 for(int i=1,p=0;i<=l[x];i++) 41 { 42 while(c2[p+1]!=s[x][i] && p) p=nxt[p]; 43 if(c2[p+1]==s[x][i]) p++; 44 // td[i]=p; 45 if(p==cl) return 1; 46 } 47 return 0; 48 } 49 50 bool check(int len) 51 { 52 for(int i=1;i+len-1<=l[id];i++) 53 { 54 cl=0; 55 for(int j=i;j<=i+len-1;j++) 56 c1[++cl]=s[id][j],c2[len-cl+1]=s[id][j]; 57 kmp_nt(); 58 bool bk=1; 59 for(int j=1;j<=n;j++) 60 if(!kmp_td(j)) {bk=0;break;} 61 if(bk) return 1; 62 } 63 } 64 65 int main() 66 { 67 freopen("a.in","r",stdin); 68 freopen("vio.out","w",stdout); 69 int T; 70 scanf("%d",&T); 71 while(T--) 72 { 73 scanf("%d",&n); 74 int ll=0,rr=Inf,mid; 75 for(int i=1;i<=n;i++) 76 { 77 scanf("%s",s[i]+1); 78 l[i]=strlen(s[i]+1); 79 if(l[i]<rr) rr=l[i],id=i; 80 } 81 while(ll<rr) 82 { 83 mid=(ll+rr+1)/2; 84 if(check(mid)) ll=mid; 85 else rr=mid-1; 86 } 87 printf("%d ",ll); 88 } 89 return 0; 90 }