POJ 3261 USACO 2006 December Gold Milk Patterns

题目大意：给出一个字符串，求出出现过k次以上的最长的子串(可重叠).

思路：现弄出来sa数组和height数组，之后就是判断每个长度为k的height数组的区间中最小的数字的最大值了.为什么好多人都二分了?这只要单调队列扫一次就行了啊..

CODE:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 1000010
using namespace std;

int len,k;
int s[MAX],val[MAX],sa[MAX];
int rank[MAX],height[MAX];

inline bool Same(int x,int y,int l)
{
	return val[x] == val[y] && 
	((x + l >= len && y + l >= len) || (x + l < len && y + l < len && val[x + l] == val[y + l]));
}

void GetSuffixArray()
{
	static int _val[MAX],cnt[MAX],q[MAX],lim = 1000001;
	for(int i = 0; i < len; ++i)	++cnt[val[i] = s[i]];
	for(int i = 1; i < lim; ++i)	cnt[i] += cnt[i - 1];
	for(int i = len - 1; ~i; --i)	sa[--cnt[val[i]]] = i;
	for(int d = 1;; ++d) {
		int top = 0,l = 1 << (d - 1);
		for(int i = 0; i < len; ++i)	if(sa[i] + l >= len)	q[top++] = sa[i];
		for(int i = 0; i < len; ++i)	if(sa[i] >= l)	q[top++] = sa[i] - l;
		
		for(int i = 0; i < lim; ++i)	cnt[i] = 0;
		for(int i = 0; i < len; ++i)	++cnt[val[q[i]]];
		for(int i = 1; i < len; ++i)	cnt[i] += cnt[i - 1];
		for(int i = len - 1; ~i; --i)	sa[--cnt[val[q[i]]]] = q[i];
		lim = 0;
		for(int i = 0,j; i < len; ++lim) {
			for(j = i; j < len - 1 && Same(sa[j],sa[j + 1],l); ++j);
			for(; i <= j; ++i)	_val[sa[i]] = lim;
		}
		for(int i = 0; i < len; ++i)	val[i] = _val[i];
		if(lim == len)	break;
	}
	return ;
}

void GetHeight()
{
	for(int i = 0; i < len; ++i)	rank[sa[i]] = i;
	for(int k = 0,i = 0; i < len; ++i) {
		if(k)	--k;
		int j = sa[rank[i] - 1];
		while(s[i + k] == s[j + k])	++k;
		height[rank[i]] = k;
	}
}

struct Complex{
	int pos,val;
	
	Complex(int _,int __):pos(_),val(__) {}
	Complex() {}
};

int main()
{
	cin >> len >> k;
	for(int i = 0; i < len; ++i)
		scanf("%d",&s[i]);
	GetSuffixArray();
	GetHeight();
	deque<Complex> q;
	int ans = 0;
	for(int i = 0; i < len; ++i) {
		while(!q.empty() && height[i] <= q.back().val)	q.pop_back();
		while(!q.empty() && i - q.front().pos >= k - 1)		q.pop_front();
		q.push_back(Complex(i,height[i]));
		ans = max(ans,q.front().val);
	}
	cout << ans << endl;
	return 0;
}

原文：http://blog.csdn.net/jiangyuze831/article/details/41802433