[Poj1743] [后缀数组论文例题] Musical Theme [后缀数组不可重叠最长重复子串]

利用后缀数组，先对读入整数处理str[i]=str[i+1]-str[i]+90这样可以避免负数，计算Height数组，二分答案，如果某处H<lim则将H数组分开，最终分成若干块，判断每块中是否存在SA[i]-SA[j]>lim（注意不是>=因为查分后如果相等那么两个公共串连接部分的元素是公用的，不符合题意），注意特判n=1的情况，因为查分后的结果是个空串，会导致RE。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <ctime>
  8 
  9 using namespace std;
 10 
 11 int    A[21000],B[21000],U[21000],SA[21000],H[21000];
 12 int    str[21000];
 13 
 14 void    Calc_H(const int n,const int * Rank)
 15 {
 16     int    i,j,k=0;
 17     for(i=0;i<n;H[Rank[i++]]=k)
 18         for(k?k--:0,j=SA[Rank[i]-1];str[i+k]==str[j+k];++k);
 19     return ;
 20 }
 21 
 22 bool    cmp(const int * s,const int a,const int b,const int l)
 23 {
 24     return    s[a]==s[b] && s[a+l]==s[b+l];
 25 }
 26 
 27 int*    Get_SA(const int n,int m)
 28 {
 29     int    i,j,p,*x=A,*y=B;
 30     memset(U,0,sizeof(U));
 31     for(i=0;i<n;++i)U[x[i]=str[i]]++;
 32     for(i=1;i<m;++i)U[i]+=U[i-1];
 33     for(i=n-1;i>=0;--i)SA[--U[x[i]]]=i;
 34 
 35     for(j=1,p=1;p<n;j<<=1,m=p)
 36     {
 37         for(p=0,i=n-j;i<n;i++)y[p++]=i;
 38         for(i=0;i<n;++i)if(SA[i]>=j)y[p++]=SA[i]-j;
 39         for(i=0;i<m;++i)U[i]=0;
 40         for(i=0;i<n;++i)U[x[y[i]]]++;
 41         for(i=1;i<m;++i)U[i]+=U[i-1];
 42         for(i=n-1;i>=0;--i)SA[--U[x[y[i]]]]=y[i];
 43         for(swap(x,y),p=1,x[SA[0]]=0,i=1;i<n;++i)
 44             x[SA[i]]=cmp(y,SA[i-1],SA[i],j)?p-1:p++;
 45     }
 46     Calc_H(n,x);
 47     return x;
 48 }
 49 
 50 bool    Check(const int lim,const int n)
 51 {
 52     int    Min=SA[1],Max=SA[1];
 53     for(int i=1;i<=n;++i)
 54     {
 55         if(i>1 && H[i]<lim)
 56         {
 57             if(Max-Min>=lim+1)return true;
 58             Min=0x7fffffff;
 59             Max=-1;
 60         }
 61         if(SA[i]<Min)Min=SA[i];
 62         if(SA[i]>Max)Max=SA[i];
 63     }
 64     if(Max-Min>lim)return true;
 65     return false;
 66 }
 67 
 68 void    Init()
 69 {
 70     memset(A,0,sizeof(A));
 71     memset(B,0,sizeof(B));
 72     memset(U,0,sizeof(U));
 73     memset(H,0,sizeof(H));
 74     memset(SA,0,sizeof(SA));
 75     return ;
 76 }
 77 
 78 int main()
 79 {
 80     int    n,i,l,r;
 81 
 82     while(~scanf("%d",&n) && n)
 83     {
 84         Init();
 85         for(i=0;i<n;++i)scanf("%d",&str[i]);
 86         if(n==1){printf("0
");continue;}
 87         n--;
 88         for(i=0;i<n;++i)str[i]=str[i+1]-str[i]+90;
 89         str[n]=0;
 90 
 91         Get_SA(n+1,200);
 92 
 93         l=0,r=n;
 94         while(l<r-1)
 95         {
 96             int    mid=l+((r-l)>>1);
 97             if(Check(mid,n))l=mid;
 98             else        r=mid;
 99         }
100         printf("%d
",l>=4 ? l+1:0);
101     }
102 
103     return 0;
104 }

View Code

[Poj1743] [后缀数组论文例题] Musical Theme [后缀数组不可重叠最长重复子串]

相关推荐