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\n",sl);continue;}105         get_sa(300);106         get_h();107         // for(int i=1;i<=cl;i++) printf("%c",c[i]);printf("\n");108         // for(int i=1;i<=cl;i++) printf("%d ",c[i]);printf("\n");109         // for(int i=1;i<=cl;i++) printf("%d ",sa[i]);printf("\n");110         // for(int i=1;i<=cl;i++) printf("%d ",rk[i]);printf("\n");111         // for(int i=1;i<=cl;i++) printf("%d ",h[i]);printf("\n");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\n",l);120     }121     return 0;122 }

 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\n",ll);88     }89     return 0;90 }