POJ3261 Milk Patterns 【后缀数组】

牛奶模式

时间限制： 5000MS		内存限制： 65536K
提交总数： 16796		接受： 7422
案件时间限制： 2000MS

描述

农夫约翰已经注意到，他的牛奶的质量每天都在变化。经进一步调查，他发现虽然不能预测一天到下一天的牛奶质量，但每天的牛奶质量有一些规律。

要执行严格的研究，他已经发明了其中每个奶样本被记录为0到1,000,000之间的整数一个复杂的分类方案，并且已经从单一的母牛超过记录数据Ñ（1≤ Ñ ≤20000）天。他希望找到其等同至少K（2≤重复样品的最长图案ķ ≤ Ñ）次。这可能包括重叠模式
- 例如，1 2 3 2 3 2 3 1重复2 3 2 3。

通过找到样本序列中最长的重复子序列来帮助Farmer John。保证至少有一个子序列重复至少K次。

输入

第1行：两个空格分隔的整数：N和K

第2行N + 1：N个整数，每行一个，第i天的牛奶质量出现在第i行。

产量

第1行：一个整数，至少出现K次的最长模式的长度

示例输入

示例输出

开心，1A后缀数组【后缀数组还很渣。。】，虽然是一道板题 + 水题

题目所求就是出现K次的最长子串

我们求出height后二分答案

对于二分出来的长度len，我们尝试在height数组中连续找出K个height[i] >= len，如果找得到，说明存在长度为len的子串重复了至少K次

最后就是答案了【是不是很水> <】

【题外：

本蒟蒻现在要开始刷后缀数组！！谁也阻挡不了我> <

搜索BZOJ后缀数组：P4310 P3230 P4698 P2946 P2251 P4556 P4270 P4516

nice，开刷

唔？4310去哪了

3230怎么也找不到。。。。。。。。

。。。。。。。。

~~没有权限的悲哀~~

看来真的要节衣缩食买个权限狗了>＜

先刷刷POJ吧。。。。

】

哦代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)

using namespace std;

const int maxn = 20005,maxm = 1000005,INF = 1000000000;

inline int RD(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

	return out * flag;

}

int n,K,A[maxn],sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],m = 0,c[maxm];

void SA(){

	int *x = t1,*y = t2;

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

	for (int i = 1; i <= n; i++) c[x[i] = A[i]]++;

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

	for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;

	for (int k = 1; k <= n; k++){

		int p = 0;

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

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

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

		for (int i = 1; i <= n; i++) c[x[y[i]]]++;

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

		for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];

		swap(x,y);

		p = 1; x[sa[1]] = 1;

		for (int i = 2; i <= n; i++)

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

		if (p >= n) break;

		m = p;

	}

	for (int i = 1; i <= n; i++) rank[sa[i]] = i;

	int k = 0;

	for (int i = 2; i <= n; i++){

		if (k) k--;

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

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

		height[rank[i]] = k;

	}

}

bool check(int len){

	int cnt = 1;

	for (int i = 2; i <= n; i++)

		if (height[i] >= len) {cnt++;if (cnt >= K) return true;}

		else cnt = 1;

	return false;

}

int main(){

	n = RD(); K = RD();

	REP(i,n) m = max(m,A[i] = RD());

	SA();

	int l = 1,r = n,mid;

	while (l < r){

		mid = l + r + 1 >> 1;

		if (check(mid)) l = mid;

		else r = mid - 1;

	}

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

	return 0;

}

巴特西

POJ3261 Milk Patterns 【后缀数组】

最新文章

热门文章