POJ-3261 Milk Patterns（后缀数组）

题目大意：找出至少出现K次的子串的最长长度。

题目分析：二分枚举长度x，判断有没有最长公共前缀不小于x的并且连续出现了至少k次的有序子串区间。

代码如下：

# include<iostream>

# include<cstdio>

# include<map>

# include<vector>

# include<cstring>

# include<algorithm>

using namespace std;

# define mid (l+(r-l)/2)

const int N=20000;

int SA[N+5],cnt[N+5];

int rk[N+5],tSA[N+5];

int a[N+5],height[N+5],n;

bool same(int i,int j,int k)

{

	if(tSA[i]!=tSA[j]) return false;

	if(i+k>=n&&j+k>=n) return true;

	if(i+k>=n&&j+k<n) return false;

	if(i+k<n&&j+k>=n) return false;

	return tSA[i+k]==tSA[j+k];

}

void buildSA(int m)

{

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

	for(int i=0;i<n;++i) ++cnt[rk[i]=a[i]];

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

	for(int i=n-1;i>=0;--i) SA[--cnt[rk[i]]]=i;

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

		int p=0;

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

		for(int i=0;i<n;++i) if(SA[i]>=k) tSA[p++]=SA[i]-k;

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

		for(int i=0;i<n;++i) ++cnt[rk[tSA[i]]];

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

		for(int i=n-1;i>=0;--i) SA[--cnt[rk[tSA[i]]]]=tSA[i];

		p=1;

		swap(rk,tSA);

		rk[SA[0]]=0;

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

			rk[SA[i]]=same(SA[i],SA[i-1],k)?p-1:p++;

		if(p>=n) break;

		m=p;

	}

}

void getHeight()

{

	for(int i=0;i<n;++i) rk[SA[i]]=i;

	int k=0;

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

		if(rk[i]==0){

			k=height[rk[i]]=0;

		}else{

			if(k) --k;

			int j=SA[rk[i]-1];

			while(i+k<n&&j+k<n&&a[i+k]==a[j+k])

				++k;

			height[rk[i]]=k;

		}

	}

}

bool ok(int x,int k)

{

	int m=(n-SA[0]>=x)?1:0;

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

		if(m>=k) return true;

		if(height[i]>=x) ++m;

		else m=(n-SA[i]>=x)?1:0;

	}

	return m>=k;

}

int main()

{

	int k;

	while(~scanf("%d%d",&n,&k))

	{

		int m=0;

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

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

			m=max(m,a[i]);

		}

		buildSA(m+1);

		getHeight();

		int l=1,r=n+1;

		while(l<r){

			if(ok(mid,k)) l=mid+1;

			else r=mid;

		}

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

	}

	return 0;

}