【SPOJ】220 Relevant Phrases of Annihilation

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 #define MAXN 10010
  6 #define MAXM 10
  7 #define MAXL 100100
  8 #define INF 123456789
  9 char s[MAXL],str[MAXM][MAXN];
 10 int m,len[MAXM];
 11 int wa[MAXL],wb[MAXL],wv[MAXL],ws[MAXL];
 12 int sa[MAXL],height[MAXL],rk[MAXL];
 13 inline bool cmp(int *r,int a,int b,int L)
 14 {
 15     return r[a]==r[b]&&r[a+L]==r[b+L];
 16 }
 17 void SA(int n,int m)
 18 {
 19     int i,j,p,*x=wa,*y=wb,*t;
 20     for(i=0;i<m;i++)
 21         ws[i]=0;
 22     for(i=0;i<n;i++)
 23         ws[x[i]=s[i]]++;
 24     for(i=1;i<m;i++)
 25         ws[i]+=ws[i-1];
 26     for(i=n-1;i>=0;i--)
 27         sa[--ws[x[i]]]=i;
 28     for(j=p=1;p<n;j<<=1,m=p)
 29     {
 30         for(p=0,i=n-j;i<n;i++)
 31             y[p++]=i;
 32         for(i=0;i<n;i++)
 33         {
 34             if(sa[i]>=j)
 35                 y[p++]=sa[i]-j;
 36         }
 37         for(i=0;i<m;i++)
 38             ws[i]=0;
 39         for(i=0;i<n;i++)
 40             ws[wv[i]=x[y[i]]]++;
 41         for(i=1;i<m;i++)
 42             ws[i]+=ws[i-1];
 43         for(i=n-1;i>=0;i--)
 44             sa[--ws[wv[i]]]=y[i];
 45         for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)
 46             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
 47     }
 48 }
 49 void Height(int n)
 50 {
 51     int i,j,k;
 52     for(i=1;i<=n;i++)
 53         rk[sa[i]]=i;
 54     for(i=k=0;i<n;height[rk[i++]]=k)
 55         for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
 56 }
 57 bool OK(int n,int mid)
 58 {
 59     int i,j,k,t;
 60     int a[MAXM][2];
 61     for(i=1;i<=n;i++)
 62     {
 63         if(height[i]>=mid)
 64         {
 65             for(j=i;j<=n&&height[j]>=mid;j++);
 66             for(k=0;k<m;k++)
 67             {    
 68                 a[k][0]=INF;
 69                 a[k][1]=0;
 70             }
 71             for(k=i-1;k<j;k++)
 72             {
 73                 t=upper_bound(len,len+m,sa[k])-len;
 74                 a[t][0]=min(a[t][0],sa[k]);
 75                 a[t][1]=max(a[t][1],sa[k]);
 76             }
 77             for(k=0;k<m;k++)
 78             {
 79                 if(a[k][1]-a[k][0]<mid)
 80                     break;
 81             }
 82             if(k==m)
 83                 return true;
 84             i=j-1;
 85         }
 86     }
 87     return false;
 88 }
 89 int main()
 90 {
 91     int c,n,i,low,high,mid,ans;
 92     scanf("%d",&c);
 93     while(c--)
 94     {
 95         scanf("%d",&m);
 96         high=INF;
 97         for(s[0]=i=0;i<m;i++)
 98         {
 99             scanf(" %s",str[i]);
100             n=strlen(str[i]);
101             high=min(high,(n>>1)+1);
102             str[i][n]=i+1;
103             str[i][n+1]=0;
104             strcat(s,str[i]);
105             len[i]=strlen(s);
106         }
107         n=len[i-1]-1;
108         s[n]=0;
109         SA(n+1,'z'+1);
110         Height(n);
111         for(low=0;low<high;)
112         {
113             mid=(high+low)>>1;
114             if(OK(n,mid))
115                 low=mid+1;
116             else
117                 high=mid;
118         }
119         ans=max(low-1,0);
120         printf("%d\n",ans);
121     }
122     return 0;
123 }