题目链接：http://poj.org/problem?id=1226

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

思路：二分。

int r[N],sa[N],wa[N],wb[N],wd[N],rank[N],h[N];int cmp(int *r,int a,int b,int len){    return r[a]==r[b]&&r[a+len]==r[b+len];}void da(int *r,int *sa,int n,int m){    int i,j,p,*x=wa,*y=wb,*t;    FOR0(i,m) wd[i]=0;    FOR0(i,n) wd[x[i]=r[i]]++;    FOR1(i,m-1) wd[i]+=wd[i-1];    FORL0(i,n-1) sa[--wd[x[i]]]=i;    for(j=1,p=1;p
     
      <<=1,m=p)    {        p=0;        FOR(i,n-j,n-1) y[p++]=i;        FOR0(i,n) if(sa[i]>=j) y[p++]=sa[i]-j;        FOR0(i,m) wd[i]=0;        FOR0(i,n) wd[x[i]]++;        FOR1(i,m-1) wd[i]+=wd[i-1];        FORL0(i,n-1) sa[--wd[x[y[i]]]]=y[i];        t=x;x=y;y=t;p=1;x[sa[0]]=0;        FOR1(i,n-1) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;    }}void calHeight(int *r,int *sa,int n){    int i,j,k=0;    FOR1(i,n) rank[sa[i]]=i;    FOR0(i,n)    {        if(k) k--;        j=sa[rank[i]-1];        while(i+k
      
       
        m) break;        R=L;        while(R<=m&&h[R]>=x) R++;        clr(hash,0);        FOR(j,L-1,R-1) if(b[sa[j]]!=-1)        {            hash[b[sa[j]]]=1;        }        FOR1(j,n) if(!hash[j]) break;        if(j>n) return 1;        i=R;    }    return 0;}void deal(){    int low=0,high=100,mid;    while(low<=high)    {        mid=(low+high)>>1;        if(OK(mid)) low=mid+1;        else high=mid-1;    }    if(low<=100&&OK(low)) PR(low);    else if(high>=0&&OK(high)) PR(high);}int main(){    int C;    RD(C);    while(C--)    {        RD(n);        int i,j,L=0,len,Max=130;        FOR1(i,n)        {            RD(s); len=strlen(s);            FOR0(j,len) r[L++]=s[j],b[L-1]=i;            r[L++]=Max++;            b[L-1]=-1;            FORL0(j,len-1) r[L++]=s[j],b[L-1]=i;            r[L++]=Max++;            b[L-1]=-1;        }        r[L]=0;        da(r,sa,L+1,Max);        calHeight(r,sa,L);        m=L;        deal();    }    return 0;}