POJ 1225 Substrings

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

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

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

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 int num[],ws[],wv[],wb[],wa[];

 int n,m,rank[],sa[],h[],b[];

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 bool cmp(int *r,int a,int b,int l){

     return r[a]==r[b]&&r[a+l]==r[b+l];

 }

 void da(int *r,int *sa,int n,int m){

     int *y=wb,*x=wa,*t,i,j,p;

     for (i=;i<m;i++) ws[i]=;

     for (i=;i<n;i++) x[i]=r[i];

     for (i=;i<n;i++) ws[x[i]]++;

     for (i=;i<m;i++) ws[i]+=ws[i-];

     for (i=n-;i>=;i--) sa[--ws[x[i]]]=i;

     for (p=,j=;p<n;m=p,j*=){

         for (p=,i=n-j;i<n;i++) y[p++]=i;

         for (i=;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;

         for (i=;i<m;i++) ws[i]=;

         for (i=;i<n;i++) wv[i]=x[y[i]];

         for (i=;i<n;i++) ws[wv[i]]++;

         for (i=;i<m;i++) ws[i]+=ws[i-];

         for (i=n-;i>=;i--) sa[--ws[wv[i]]]=y[i];

         for (t=x,x=y,y=t,i=,p=,x[sa[]]=;i<n;i++)

          x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;

     }

 }

 void cal(int *r,int n){

     int i,j,k=;

     for (i=;i<=n;i++) rank[sa[i]]=i;

     for (i=;i<n;h[rank[i++]]=k)

      for (k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k];k++);

 }

 bool check(int x){

     int L,R;

     int hash[];

     for (int i=;i<=n;i++){

         L=i;

         while (L<=n&&h[L]<x) L++;

         if (L>n) break;

         R=L;

         while (R<=n&&h[R]>=x) R++;

         memset(hash,,sizeof hash);

         for (int j=L-;j<=R-;j++)

          if (b[sa[j]]<=m)

           hash[b[sa[j]]]=;

         int j=;

         for (j=;j<=m;j++)

          if (!hash[j]) break;

         if (j>m) return ;

         i=R;

     }

     return ;

 }

 void solve(){

     int l=,r=,ans;

     while (l<=r){

         int mid=(l+r)>>;

         if (check(mid)) ans=mid,l=mid+;

         else r=mid-;

     }

     printf("%d\n",ans);

 }

 int main(){

     int T=read();

     char s[];

     while (T--){

         m=read();n=;int sx=;

         for (int i=;i<=m;i++){

             scanf("%s",s);

             int len=strlen(s);

             for (int j=;j<len;j++)

              num[n]=s[j],b[n++]=i;

             num[n]=sx++;b[n++]=n+;

             for (int j=len-;j>=;j--)

              num[n]=s[j],b[n++]=i;

             num[n]=sx++;b[n++]=n+;

         }

         num[n]=;b[n]=n+;

         da(num,sa,n+,sx+);

         cal(num,n);

         solve();

     }

 }