后缀数组专题练习

poj 1743 Musical Theme （后缀数组+二分）

题目：http://poj.org/problem?id=1743

题意：一篇n个音符的乐谱，求他最长的音乐主题（两端变化相同的长度大于五的不重合乐谱）

思路：09年论文后缀数组的题目：先二分答案，变成判定性问题，判断是否存在两个长度为k的子串是相同的，且不重叠。解决这个问题的关键利用height数组；

把排序后的后缀分成若干组，其中每组的后缀之间的height值都不小于k；

若有一组中最小的sa和最大的sa之差大于等于k，则存在。

代码：

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<stack>
  7 #include<cmath>
  8 #include<stdlib.h>
  9 using namespace std;
 10 const int maxn=20010;
 11 int wa[maxn],wb[maxn],wv[maxn],wws[maxn];
 12 int sa[maxn],rank[maxn];
 13 int height[maxn];
 14 int abs(int a)
 15 {
 16     if(a<0) return -a;
 17     else  return a;
 18 }
 19 int cmp(int *r,int a,int b,int l)
 20 {
 21     return r[a]==r[b]&&r[a+l]==r[b+l];
 22 }
 23 void da(int *r,int n,int m)
 24 {
 25     int i,j,p,*x=wa,*y=wb,*t;
 26     for(i=0;i<m;i++) wws[i]=0;
 27     for(i=0;i<n;i++) wws[x[i]=r[i]]++;
 28     for(i=1;i<m;i++) wws[i]+=wws[i-1];
 29     for(i=n-1;i>=0;i--) sa[--wws[x[i]]]=i;
 30     for(j=1,p=1;p<n;j*=2,m=p)
 31     {
 32         for(p=0,i=n-j;i<n;i++) y[p++]=i;
 33         for(i=0;i<n;i++)
 34         if(sa[i]>=j) y[p++]=sa[i]-j;
 35         for(i=0;i<n;i++) wv[i]=x[y[i]];
 36         for(i=0;i<m;i++) wws[i]=0;
 37         for(i=0;i<n;i++) wws[wv[i]]++;
 38         for(i=1;i<m;i++) wws[i]+=wws[i-1];
 39         for(i=n-1;i>=0;i--)
 40         sa[--wws[wv[i]]]=y[i];
 41         t=x,x=y,y=t;
 42         p=1;
 43         x[sa[0]]=0;
 44         for(i=1;i<n;i++)
 45         x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
 46     }
 47     return ;
 48 }
 49 void calheight(int *r,int n)
 50 {
 51     int i,j,k=0;
 52     for(i=1;i<=n;i++)
 53     {
 54         rank[sa[i]]=i;
 55     }
 56     for(i=0;i<n;height[rank[i++]]=k)
 57     {
 58         for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
 59     }
 60     return ;
 61 }
 62 bool juge(int m,int n)
 63 {
 64     int i,j;
 65     for(i=2;i<=n;i++)
 66     {
 67         if(height[i]<m) continue;//相当于分组
 68         for(j=i-1;j>=2;j--)
 69         {
 70             if(abs(sa[i]-sa[j])>=m)
 71             return true;
 72             if(height[j]<m)//不在同一组跳出
 73             break;
 74         }
 75     }
 76     return false;
 77 }
 78 void binary(int n)
 79 {
 80     int l,r;
 81     l=3;r=n;
 82     int ans=0;
 83     while(l<=r)
 84     {
 85         int m=(l+r)/2;
 86         if(juge(m,n))
 87         {
 88             l=m+1;
 89             ans=m;
 90         }
 91         else
 92         r=m-1;
 93     }
 94     if(ans<4)
 95     printf("0
");
 96     else
 97     printf("%d
",ans+1);
 98 
 99 }
100 int main()
101 {
102     int n;
103     int data[maxn];
104     while(scanf("%d",&n)!=EOF)
105     {
106         if(n==0)
107         break;
108         int i;
109         n--;
110         for(i=0;i<=n;i++)
111         scanf("%d",&data[i]);
112         if(n<10)
113         {
114             printf("0
");
115             continue;
116         }
117         for(i=0;i<n;i++)
118         data[i]=data[i+1]-data[i]+90;
119         data[n]=0;//小技巧，防止数组越界
120         da(data,n+1,190);//求出后缀数组
121         calheight(data,n);//求出height数组
122         binary(n);//进行二分
123     }
124     return 0;
125 }

View Code

poj 3261 Milk Patterns（后缀数组+二分）

题目：http://poj.org/problem?id=3261

题意：给定一个字符串，求至少出现k次的最长重复子串，这k个子串可以重叠

思路：与1743做法差不多，只是在判断的时候有没有一个组的后缀个数大于等于k，若有则满足

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<stack>
  7 #include<cmath>
  8 #include<stdlib.h>
  9 using namespace std;
 10 const int maxn=20010;
 11 const int mmaxn=1000010;
 12 int wa[maxn],wb[maxn],wv[maxn],wws[mmaxn];
 13 int sa[maxn],rank[maxn];
 14 int height[maxn];
 15 int abs(int a)
 16 {
 17     if(a<0) return -a;
 18     else  return a;
 19 }
 20 int cmp(int *r,int a,int b,int l)
 21 {
 22     return r[a]==r[b]&&r[a+l]==r[b+l];
 23 }
 24 void da(int *r,int n,int m)//传入时r[n-1]=0,其他>0;n为长度，m为字符的范围
 25 {
 26     int i,j,p,*x=wa,*y=wb,*t;
 27     for(i=0; i<m; i++) wws[i]=0;
 28     for(i=0; i<n; i++) wws[x[i]=r[i]]++;
 29     for(i=1; i<m; i++) wws[i]+=wws[i-1];
 30     for(i=n-1; i>=0; i--) sa[--wws[x[i]]]=i;
 31     for(j=1,p=1; p<n; j*=2,m=p)
 32     {
 33         for(p=0,i=n-j; i<n; i++) y[p++]=i;
 34         for(i=0; i<n; i++)
 35             if(sa[i]>=j) y[p++]=sa[i]-j;
 36         for(i=0; i<n; i++) wv[i]=x[y[i]];
 37         for(i=0; i<m; i++) wws[i]=0;
 38         for(i=0; i<n; i++) wws[wv[i]]++;
 39         for(i=1; i<m; i++) wws[i]+=wws[i-1];
 40         for(i=n-1; i>=0; i--) sa[--wws[wv[i]]]=y[i];
 41         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
 42 
 43     }
 44     return ;
 45 }
 46 void calheight(int *r,int n)//n要小1
 47 {
 48     int i,j,k=0;
 49     for(i=1; i<=n; i++) rank[sa[i]]=i; //注意循环条件
 50     for(i=0; i<n; height[rank[i++]]=k)
 51         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++); //不要忘记分号
 52 }
 53 bool juge(int m,int n,int K)
 54 {
 55     int i,j;
 56     int sum=0;
 57     for(i=1; i<=n; i++)
 58     {
 59         if(height[i]>=m)
 60         {
 61             sum++;
 62             if(sum==K-1)
 63                 return true;
 64         }
 65         else
 66             sum=0;
 67     }
 68     return false;
 69 }
 70 void binary(int n,int K)
 71 {
 72     int l,r;
 73     l=1;
 74     r=n;
 75     int ans=0;
 76     while(l<=r)
 77     {
 78         int m=(l+r)/2;
 79         if(juge(m,n,K))
 80         {
 81             l=m+1;
 82             ans=m;
 83         }
 84         else
 85             r=m-1;
 86     }
 87     printf("%d
",ans);
 88 
 89 }
 90 int main()
 91 {
 92     int n,K;
 93     int data[maxn];
 94     while(scanf("%d%d",&n,&K)!=EOF)
 95     {
 96         int i;
 97         for(i=0; i<n; i++)
 98         {
 99             scanf("%d",&data[i]);
100             data[i]++;
101         }
102         data[n]=0;//小技巧，防止数组越界
103         da(data,n+1,mmaxn-5);//求出后缀数组
104         calheight(data,n);//求出height数组
105         binary(n,K);//进行二分
106     }
107     return 0;
108 }

View Code

poj 2406 Power Strings(后缀数组+枚举)

题目：http://poj.org/problem?id=2406

题意：一个字符串由某个字符串S重复R次得到，求R的最大值

思路：枚举字符串S的长度k,看suffix（1）和suffix（k+1）的最长公共前缀是否等于n-k（倍增算法超时，用DC3算法）

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<stack>
  7 #include<cmath>
  8 #include<stdlib.h>
  9 #define F(x) ((x)/3+((x)%3==1?0:tb))
 10 #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
 11 using namespace std;
 12 const int maxn=1000010;
 13 char str[maxn];
 14 int wa[maxn*3],wb[maxn*3],wv[maxn*3],wws[maxn];
 15 int data[maxn*3];
 16 int sa[maxn*3],rank[maxn],height[maxn];
 17 int res[maxn];
 18 int c0(int *r,int a,int b)
 19 {
 20     return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
 21 }
 22 int c12(int k,int *r,int a,int b)
 23 {
 24     if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
 25     else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
 26 }
 27 void sort(int *r,int *a,int *b,int n,int m)
 28 {
 29     int i;
 30     for(i=0; i<n; i++) wv[i]=r[a[i]];
 31     for(i=0; i<m; i++) wws[i]=0;
 32     for(i=0; i<n; i++) wws[wv[i]]++;
 33     for(i=1; i<m; i++) wws[i]+=wws[i-1];
 34     for(i=n-1; i>=0; i--) b[--wws[wv[i]]]=a[i];
 35     return ;
 36 }
 37 void dc3(int *r,int *sa,int n,int m)
 38 {
 39     int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
 40     r[n]=r[n+1]=0;
 41     for(i=0; i<n; i++) if(i%3!=0) wa[tbc++]=i;
 42     sort(r+2,wa,wb,tbc,m);
 43     sort(r+1,wb,wa,tbc,m);
 44     sort(r,wa,wb,tbc,m);
 45     for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)
 46         rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
 47     if(p<tbc) dc3(rn,san,tbc,p);
 48     else for(i=0; i<tbc; i++) san[rn[i]]=i;
 49     for(i=0; i<tbc; i++) if(san[i]<tb) wb[ta++]=san[i]*3;
 50     if(n%3==1) wb[ta++]=n-1;
 51     sort(r,wb,wa,ta,m);
 52     for(i=0; i<tbc; i++) wv[wb[i]=G(san[i])]=i;
 53     for(i=0,j=0,p=0; i<ta&&j<tbc; p++)
 54         sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
 55     for(; i<ta; p++) sa[p]=wa[i++];
 56     for(; j<tbc; p++) sa[p]=wb[j++];
 57     return ;
 58 }
 59 
 60 
 61 void calheight(int *r,int n,int m)
 62 {
 63     int i,j,k=0;
 64     for(i=1; i<=n; i++) rank[sa[i]]=i;
 65     for(i=0; i<n; height[rank[i++]]=k)
 66         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
 67 }
 68 void run(int n)
 69 {
 70     int s=rank[0];
 71     //printf("s=%d
",s);
 72     int min=maxn+10;
 73     int i;
 74     res[s]=n;
 75     for(i=s-1; i>=0; i--)
 76     {
 77         if(min>height[i+1])
 78             min=height[i+1];
 79         res[i]=min;
 80     }
 81     min=maxn+10;
 82     for(i=s+1; i<=n; i++)
 83     {
 84         if(min>height[i])
 85             min=height[i];
 86         res[i]=min;
 87     }
 88     return ;
 89 }
 90 int main()
 91 {
 92     while(scanf("%s%*c",str)!=EOF)
 93     {
 94         if(str[0]=='.')
 95             break;
 96         int len=strlen(str);
 97         int i;
 98         int mmax=0;
 99         for(i=0; i<len; i++)
100         {
101             data[i]=str[i]-'a'+1;
102             if(mmax<data[i])
103                 mmax=data[i];
104         }
105         data[len]=0;
106         dc3(data,sa,len+1,mmax+1);
107         calheight(data,len,mmax+1);
108         /*printf("sa  ");
109         for(i=0;i<=len;i++)
110             printf("%d ",sa[i]);
111         printf("
");
112         printf("rank");
113         for(i=0;i<=len;i++)
114             printf("%d ",rank[i]);
115         printf("
");
116         printf("he  ");
117         for(i=0;i<=len;i++)
118         printf("%d ",height[i]);
119         printf("
");
120 
121         printf("re  ");
122         for(i=0;i<=len;i++)
123             printf("%d ",res[i]);
124         printf("
");*/
125         run(len);
126         for(i=1; i<=len; i++)
127         {
128             if(len%i==0&&res[rank[i]]==len-i)
129             {
130                 //printf("i=%d
",i);
131                 break;
132             }
133         }
134         if(i>=len)
135             printf("1
");
136         else
137             printf("%d
",len/i);
138     }
139     return 0;
140 }

View Code