poj 3261 二分答案+后缀数组 求至少出现k次的最长重复子序列

 1 #include "stdio.h"
 2 #define maxn 20010
 3 
 4 int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
 5 int rank[maxn],height[maxn];
 6 int r[maxn],sa[maxn],ans[maxn];
 7 int n,res,k;
 8 
 9 int cmp(int *r,int a,int b,int l)
10 {
11     return r[a]==r[b]&&r[a+l]==r[b+l];
12 }
13 
14 void da(int *r,int *sa,int n,int m)
15 {
16     int i,j,p,*x=wa,*y=wb,*t;
17     for(i=0; i<m; i++) ws[i]=0;
18     for(i=0; i<n; i++) ws[x[i]=r[i]]++;
19     for(i=1; i<m; i++) ws[i]+=ws[i-1];
20     for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;
21     for(j=1,p=1; p<n; j*=2,m=p)
22     {
23 
24         for(p=0,i=n-j; i<n; i++) y[p++]=i;
25         for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
26         for(i=0; i<n; i++) wv[i]=x[y[i]];
27         for(i=0; i<m; i++) ws[i]=0;
28         for(i=0; i<n; i++) ws[wv[i]]++;
29         for(i=1; i<m; i++) ws[i]+=ws[i-1];
30         for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];
31         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
32             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
33     }
34     return;
35 }
36 
37 void calheight(int *r,int *sa,int n)
38 {
39     int i,j,k=0;
40     for(i=1; i<=n; i++) rank[sa[i]]=i;
41     for(i=0; i<n; height[rank[i++]]=k)
42         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
43     return;
44 }
45 
46 bool calc(int x)        //x:length
47 {
48     int rec[maxn];
49     int nm=0;
50     for (int i=1;i<=n;i++)
51     {
52         if (height[i]<x)
53         {
54             nm++;
55             rec[nm]=i;
56         }
57     }
58     nm++;   rec[nm]=n+1;
59     for (int i=1;i<=nm;i++)
60     {
61         int tl=rec[i-1],tr=rec[i];
62         if (tr-tl>=k)      return true;
63     }
64     return false;
65 }
66 
67 int main()
68 {
69     scanf("%d %d",&n,&k);
70     for (int i=0; i<n; i++)
71         scanf("%d",&r[i]);
72     r[n]=0;
73 
74     da(r,sa,n+1,200);
75     calheight(r,sa,n);
76 
77     //TODO: Please Code Here
78     int l=0,r=n,res=0;
79     while (r>=l)
80     {
81         int mid=(l+r)/2;
82         if (calc(mid))
83         {
84             if (mid>res)    res=mid;
85             l=mid+1;
86         }
87         else
88             r=mid-1;
89     }
90     printf("%d\n",res);
91     return 0;
92 }