1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1469 Solved: 799
[Submit][Status][Discuss]

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

题意

给定一个字符串，求至少出现k次的可重叠最长重复子串。

分析

后缀数组求出height（排名相邻的两个后缀的公共前缀），二分长度，在height中O(n)判断。

要求有连续k-1个height的值大于等于当前二分的长度才可以。

时间复杂度O(nlogn)

直接二分+hash也可以，复杂度相同

code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int N = 50010;
 8 
 9 int s[N];
10 int t1[N],t2[N],c[N],sa[N],height[N],rank[N];
11 int n,m = 130,k;
12 
13 void get_sa() {
14     int i,p,*x = t1,*y = t2;
15     for (i=0; i<m; ++i) c[i] = 0;
16     for (i=0; i<n; ++i) x[i] = s[i],c[x[i]]++;
17     for (i=1; i<m; ++i) c[i] += c[i-1];
18     for (i=n-1; i>=0; --i) sa[--c[x[i]]] = i;
19     for (int k=1; k<=n; k<<=1) {
20         p = 0;
21         for (i=n-k; i<n; ++i) y[p++] = i;
22         for (i=0; i<n; ++i) if(sa[i]>=k) y[p++]=sa[i]-k;
23         for (i=0; i<m; ++i) c[i] = 0;
24         for (i=0; i<n; ++i) c[ x[y[i]] ]++;
25         for (i=1; i<m; ++i) c[i] += c[i-1];
26         for (i=n-1; i>=0; --i) sa[--c[ x[y[i]] ]] = y[i];
27         swap(x,y);
28         p = 1;
29         x[sa[0]] = 0;
30         for (i=1; i<n; ++i) 
31             x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && sa[i-1]+k<n && sa[i]+k<n &&    
32             y[sa[i-1]+k]==y[sa[i]+k]) ? p-1 : p++;        
33         if (p>=n) break;
34         m = p;
35     }
36 }
37 void get_height() {
38     for (int i=0; i<n; ++i) rank[sa[i]] = i;
39     int k = 0;
40     height[0] = 0;
41     for (int i=0; i<n; ++i) {
42         if (!rank[i]) continue;
43         if (k) k--;
44         int j = sa[rank[i]-1];
45         while (i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
46         height[rank[i]] = k;
47     }
48 }
49 bool check(int x) {
50     int num = 0;
51     for (int i=0; i<n; ++i) {
52         if (height[i] >= x) {
53             num ++;
54             if (num == k-1) return true;
55         }
56         else num = 0;
57     }
58     return false;
59 }
60 int main () {
61     scanf("%d%d",&n,&k);
62     for (int i=0; i<n; ++i) scanf("%d",&s[i]);
63     get_sa();
64     get_height();
65     int L = 1,R = n,mid,ans;
66     while (L <= R) {
67         mid = (L + R) >> 1;
68         if (check(mid)) ans = mid,L = mid + 1;
69         else R = mid - 1;
70     }
71     printf("%d",ans);
72     return 0;
73 }