题意：
n<=10,len<=100
思路：
只有一个字符串的时候特判一下
#include<cstdio> #include<cstring> #include<string> #include<cmath> #include<iostream> #include<algorithm> #include<map> #include<set> #include<queue> #include<vector> using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> PII; typedef vector<int> VI; #define fi first #define se second #define MP make_pair #define N 210000 #define MOD 1000000007 #define eps 1e-8 #define pi acos(-1) #define oo 1000000000 char ch[N]; int n,i,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],rank[N], a[N],b[N],num[N],M; int read() { int v=0,f=1; char c=getchar(); while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); return v*f; } bool cmp(int *r,int a,int b,int l) { return r[a]==r[b]&&r[a+l]==r[b+l]; } void getsa(int *r,int *sa,int n,int m) { int *x=wa,*y=wb,j,p; for(i=0;i<n;i++) wc[x[i]=r[i]]++; for(i=1;i<m;i++) wc[i]+=wc[i-1]; for(i=n-1;i>=0;i--) sa[--wc[x[i]]]=i; for(j=1,p=1;p<n;j*=2,m=p) { p=0; for(i=n-j;i<n;i++) y[p++]=i; for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0;i<n;i++) wd[i]=x[y[i]]; for(i=0;i<m;i++) wc[i]=0; for(i=0;i<n;i++) wc[wd[i]]++; for(i=1;i<m;i++) wc[i]+=wc[i-1]; for(i=n-1;i>=0;i--) sa[--wc[wd[i]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } } void getheight(int *r,int *sa,int n) { int i,j,k=0; for(i=1;i<=n;i++) rank[sa[i]]=i; for(i=0;i<n;height[rank[i++]]=k) { if(k) k--; j=sa[rank[i]-1]; while(r[i+k]==r[j+k]) k++; } } void init() { memset(s,0,sizeof(s)); memset(sa,0,sizeof(sa)); memset(wa,0,sizeof(wa)); memset(wb,0,sizeof(wb)); memset(wc,0,sizeof(wc)); memset(wd,0,sizeof(wd)); memset(height,0,sizeof(height)); memset(rank,0,sizeof(rank)); } bool isok(int K) { int i=1; while(i<n) { i++; if(height[i]>=K) { int st=i; while(i<=n&&height[i]>=K) i++; for(int j=1;j<=M;j++) b[j]=0; for(int j=max(1,st-1);j<=i-1;j++) { int t=sa[j]; b[num[t]]++; } int flag=1; for(int j=1;j<=M;j++) if(!b[j]){flag=0; break;} if(flag) return 1; } } return 0; } int main() { //freopen("poj1226.in","r",stdin); //freopen("poj1226.out","w",stdout); int cas; scanf("%d",&cas); while(cas--) { init(); scanf("%d",&M); n=-1; int p=0; for(int i=1;i<=M;i++) { scanf("%s",ch); int t=strlen(ch); if(M==1) printf("%d ",t); for(int j=0;j<t;j++) { s[++n]=ch[j]+100; num[n]=i; } s[++n]=p++; num[n]=0; for(int j=t-1;j>=0;j--) { s[++n]=ch[j]+100; num[n]=i; } s[++n]=p++; num[n]=0; } if(M==1) continue; //printf("1 "); getsa(s,sa,n+1,300); getheight(s,sa,n); //for(int i=2;i<=n;i++) printf("%d ",height[i]); int L=1; int R=100; int last=0; while(L<=R) { int mid=(L+R)>>1; if(isok(mid)){last=mid; L=mid+1;} else R=mid-1; } printf("%d ",last); memset(num,0,sizeof(num)); } return 0; }