poj 3693 后缀数组+ST

枚举长度和起点，枚举起点的时候每次+长度。这样枚举的复杂度是O(nlogn)。

难点就在如何字典序最小。 可以求一下区间的rk的最小值来找这个字典序最小的位置。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;
char s[N],s2[N];
int len;

struct ST
{
	int f[N][17];
	void make(int *a,int n)
	{
		for (int i=1;i<=n;i++) f[i][0]=a[i];
		for (int j=1;j<17;j++)
			for (int i=1;i<=n+1-(1<<j);i++)
				f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
	}
	int get(int l,int r)
	{
		int k=log(r-l+1)/log(2);
		return min(f[l][k],f[r+1-(1<<k)][k]);
	}
}HL,HR,RK;
struct suffixarray
{
	int sa[N],rk[N],h[N];
	int cnt[N],sa2[N],rk2[N];
	int n;
	bool cmp(int i,int j,int len)
	{
		if (rk2[i]==rk2[j]&&rk2[i+len]==rk2[j+len]) return 0;
		return 1;
	}
	void make(char *s,int len)
	{
		n=len;
		int m=255;
		for (int i=1;i<=m;i++) cnt[i]=0;
		for (int i=1;i<=n;i++) cnt[s[i]]++;
		for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
		for (int i=n;i>=1;i--) sa[cnt[s[i]]--]=i;
		int k=1; rk[sa[1]]=1;
		for (int i=2;i<=n;i++)
		{
			if (s[sa[i]]!=s[sa[i-1]]) k++;
			rk[sa[i]]=k;
		}
		rk2[n+1]=0;
		for (int j=1;k<n&&j<=n;j*=2)
		{
			int tot=0;
			for (int i=n-j+1;i<=n;i++) sa2[++tot]=i;
			for (int i=1;i<=n;i++)
				if (sa[i]>j) sa2[++tot]=sa[i]-j;
			m=k;
			for (int i=1;i<=m;i++) cnt[i]=0;
			for (int i=1;i<=n;i++) cnt[rk[i]]++;
			for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];
			for (int i=n;i>=1;i--) sa[ cnt[rk[sa2[i]]]-- ]=sa2[i];
			for (int i=1;i<=n;i++) rk2[i]=rk[i];
			k=1; rk[sa[1]]=1;
			for (int i=2;i<=n;i++)
			{
				if (cmp(sa[i],sa[i-1],j)) k++;
				rk[sa[i]]=k;
			}
		}
		for (int i=1;i<=n;i++)
		{
			k=h[rk[i-1]];
			if (k>0) k--;
			int j=sa[rk[i]-1];
			while(s[i+k]==s[j+k]) k++;
			h[rk[i]]=k;
		}
	}
	int lcp(ST &H,int i,int j)
	{
		int l=rk[i],r=rk[j];
		if (l>r) swap(l,r);
		return H.get(l+1,r);
	}
}SAL,SAR;
int k,idx,sl;
void solve()
{
	k=1;
	idx=1;
	sl=1;
	for (int i=2;i<=len;i++)
		if (s[i]<s[idx]) idx=i;

	HL.make(SAL.h,len);
	HR.make(SAR.h,len);
	RK.make(SAL.rk,len);
	for (int j=1;j<=len/2;j++)
	{
		for (int i=1;i<=len-j;i+=j)
		{
			if (i+j*k-1>len) break;  // 卡常数
			if (s[i]!=s[i+j]) continue;  // 卡常数
			int r=i+j+SAL.lcp(HL,i,i+j)-1;
			int l=i-SAR.lcp(HR,len+1-i,len+1-(i+j))+1;
			if ((r-l+1)/j<k) continue;
			int re=(r-l+1)%j;
			int id=RK.get(l,l+re); // 这个区间都会出现重复k次的子串，在这个区间内找字典序最小来更新答案
			if ((r-l+1)/j>k||(r-l+1)/j==k&&id<idx)
				k=(r-l+1)/j,idx=id,sl=j;
			i=max(i,r+1-j);  // 卡常数
		}
	}
	s[SAL.sa[idx]+k*sl]=0;
	printf("%s",s+SAL.sa[idx]);
	printf("\n");
}
int main()
{
	int cas=0;
	while(scanf("%s",s+1),s[1]!='#')
	{
		printf("Case %d: ",++cas);
		len=strlen(s+1);
		for (int i=1;i<=len;i++) s2[len+1-i]=s[i];
		SAL.make(s,len);
		SAR.make(s2,len);
		solve();
	}
}