BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式( 二分答案 + 后缀数组 )

二分答案m, 后缀数组求出height数组后分组来判断.

------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

const int maxn = 20009;

struct HASH {

int id[maxn], N;

HASH() {

N = 0;

}

inline void work() {

sort(id, id + N);

N = unique(id, id + N) - id;

}

inline void add(int x) {

id[N++] = x;

}

inline int hash(int x) {

return lower_bound(id, id + N, x) - id;

}

} h;

int sa[maxn], rank[maxn], height[maxn], S[maxn], cnt[maxn], N, K;

void build_sa() {

int m = h.N, *x = height, *y = rank;

for(int i = 0; i < m; i++) cnt[i] = 0;

for(int i = 0; i < N; i++) cnt[x[i] = S[i]]++;

for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];

for(int i = N - 1; ~i; i--) sa[--cnt[x[i]]] = i;

for(int k = 1; k <= N; k <<= 1) {

int p = 0;

for(int i = N - k; i < N; i++) y[p++] = i;

for(int i = 0; i < N; i++) if(sa[i] >= k) y[p++] = sa[i] - k;

for(int i = 0; i < m; i++) cnt[i] = 0;

for(int i = 0; i < N; i++) cnt[x[i]]++;

for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];

for(int i = N - 1; ~i; i--) sa[--cnt[x[y[i]]]] = y[i];

swap(x, y); p = 1; x[sa[0]] = 0;

for(int i = 1; i < N; i++)

   x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;

if(p >= N) break;

m = p;

}

}

void build_height() {

int k = 0;

for(int i = 0; i < N; i++) rank[sa[i]] = i;

for(int i = 0; i < N; i++) {

if(k) k--;

int j = sa[rank[i] - 1];

while(S[i + k] == S[j + k]) k++;

height[rank[i]] = k;

}

}

bool check(int len) {

int cnt = 1;

for(int i = 1; i < N; i++) {

if(height[i] >= len) {

   if(++cnt >= K) return true;

} else

   cnt = 1;

}

return false;

}

int main() {

scanf("%d%d", &N, &K);

for(int i = 0; i < N; i++) {

   scanf("%d", S + i);

   h.add(S[i]);

}

h.add(S[N++] = -0x7fffffff);

h.work();

for(int i = 0; i < N; i++)

   S[i] = h.hash(S[i]);

build_sa(); build_height();

int L = 0, R = N;

    while(L < R) {

int m = (L + R) / 2 + 1;

if(check(m))

   L = m;

else 

   R = m - 1;

}

printf("%d\n", L);

return 0;

}

------------------------------------------------------------

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

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 640  Solved: 358
[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

4

HINT

Source

Gold