【POJ】3261 Milk Patterns

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define MAXN 20010
 5 int in[MAXN],a[MAXN];
 6 int ws[MAXN],wv[MAXN],wa[MAXN],wb[MAXN];
 7 int sa[MAXN],Rank[MAXN],height[MAXN];
 8 int n,k;
 9 inline bool cmp(int *r,int a,int b,int len)
10 {
11     return r[a]==r[b]&&r[a+len]==r[b+len];
12 }
13 void SA(int n,int m)
14 {
15     int i,j,p,*x=wa,*y=wb,*t;
16     for(i=0;i<m;i++)
17         ws[i]=0;
18     for(i=0;i<n;i++)
19         ws[x[i]=in[i]]++;
20     for(i=1;i<m;i++)
21         ws[i]+=ws[i-1];
22     for(i=n-1;i>=0;i--)
23         sa[--ws[x[i]]]=i;
24     for(j=p=1;p<n;j<<=1,m=p)
25     {
26         for(p=0,i=n-j;i<n;i++)
27             y[p++]=i;
28         for(i=0;i<n;i++)
29         {
30             if(sa[i]>=j)
31                 y[p++]=sa[i]-j;
32         }
33         for(i=0;i<m;i++)
34             ws[i]=0;
35         for(i=0;i<n;i++)
36             ws[wv[i]=x[y[i]]]++;
37         for(i=1;i<m;i++)
38             ws[i]+=ws[i-1];
39         for(i=n-1;i>=0;i--)
40             sa[--ws[wv[i]]]=y[i];
41         for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)
42             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
43     }
44 }
45 void Height(int n)
46 {
47     int i,j,k;
48     for(i=1;i<=n;i++)
49         Rank[sa[i]]=i;
50     for(i=k=0;i<n;height[Rank[i++]]=k)
51         for(k?k--:0,j=sa[Rank[i]-1];in[i+k]==in[j+k];k++);
52 }
53 bool OK(int mid)
54 {
55     int i,cnt;
56     for(i=cnt=1;i<=n;i++)
57     {
58         if(height[i]>=mid)
59         {
60             cnt++;
61             if(cnt>=k)
62                 return true;
63         }
64         else
65             cnt=1;
66     }
67     return false;
68 }
69 int main()
70 {
71     int i,m,high,low,mid;
72     while(~scanf("%d%d",&n,&k))
73     {
74         for(i=0;i<n;i++)
75         {
76             scanf("%d",&in[i]);
77             a[i]=in[i];
78         }
79         sort(a,a+n);
80         m=unique(a,a+n)-a;
81         for(i=0;i<n;i++)
82             in[i]=lower_bound(a,a+m,in[i])-a+1;
83         a[n]=0;
84         SA(n+1,m+1);
85         Height(n);
86         for(low=0,high=n+1;low<high;)
87         {
88             mid=(low+high)>>1;
89             if(OK(mid))
90                 low=mid+1;
91             else
92                 high=mid;
93         }
94         printf("%d\n",low-1);
95     }
96     return 0;
97 }
新博客：www.zhixiangli.com