http://poj.org/problem?id=1226

题意：给定n个串。求一个最长的串，使得这个串或者其反串在每个串中都出现过？

思路：先在大串里面加入正反串，然后二分，判定即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 int num[200005],ws[200005],wv[200005],wb[200005],wa[200005]; 7 int n,m,rank[200005],sa[200005],h[200005],b[200005]; 8 int read(){ 9     int t=0,f=1;char ch=getchar();10     while (ch<'0'||ch>'9'){
   if (ch=='-')f=-1;ch=getchar();}11     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}12     return t*f;13 }14 bool cmp(int *r,int a,int b,int l){15     return r[a]==r[b]&&r[a+l]==r[b+l];16 }17 void da(int *r,int *sa,int n,int m){18     int *y=wb,*x=wa,*t,i,j,p;19     for (i=0;i
          
           =0;i--) sa[--ws[x[i]]]=i;24 for (p=1,j=1;p
           
            =j) y[p++]=sa[i]-j;27 for (i=0;i
            
             =0;i--) sa[--ws[wv[i]]]=y[i];32 for (t=x,x=y,y=t,i=1,p=1,x[sa[0]]=0;i
             
              n) break;49 R=L;50 while (R<=n&&h[R]>=x) R++;51 memset(hash,0,sizeof hash);52 for (int j=L-1;j<=R-1;j++)53 if (b[sa[j]]<=m)54 hash[b[sa[j]]]=1;55 int j=0;56 for (j=1;j<=m;j++)57 if (!hash[j]) break;58 if (j>m) return 1; 59 i=R; 60 }61 return 0;62 }63 void solve(){64 int l=0,r=100,ans;65 while (l<=r){66 int mid=(l+r)>>1;67 if (check(mid)) ans=mid,l=mid+1;68 else r=mid-1;69 }70 printf("%d\n",ans);71 }72 int main(){73 int T=read();74 char s[200005];75 while (T--){76 m=read();n=0;int sx=130;77 for (int i=1;i<=m;i++){78 scanf("%s",s);79 int len=strlen(s);80 for (int j=0;j
              
               =0;j--)84 num[n]=s[j],b[n++]=i;85 num[n]=sx++;b[n++]=n+1; 86 }87 num[n]=0;b[n]=n+1;88 da(num,sa,n+1,sx+10);89 cal(num,n);90 solve();91 }92 }