开两个后缀数组    三个RMQ可以做到nlogn（反正我写的是类，想开多少都无压力）
后缀数组记录正串与反串的后缀信息
同时对应的两个RMQ分别维护这两个后缀数组的height值的区间极值
在罗穗骞论文的基础上就可以做到找到最多的重复
另一个RMQ维护字典序的区间极值（利用正串的后缀数组的rank值维护）
这样在找到最多的重复的基础上同时保证了字典序最小


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

class Suffix_array
{
private:
	int wa[Maxn],wb[Maxn],ws[Maxn],wv[Maxn];
	bool cmp(int *r,const int &a,const int &b,const int &j)
	{
		return (r[a]==r[b] && r[a+j]==r[b+j]);
	}
public:
	int sa[Maxn],rank[Maxn],height[Maxn]; 
	void Build_Sa(char *r,int len,int m=Maxn)
	{
		len++;
		int *x=wa,*y=wb,i,j,p;
		memset(ws,0,sizeof ws);
		for(int i=0;i<len;i++) ws[x[i]=r[i]]++;
		for(int i=1;i<m;i++) ws[i]+=ws[i-1];
		for(int i=len-1;i>=0;i--) sa[--ws[x[i]]]=i;

		for(j=1,p=0;p<len;j*=2,m=p)
		{
			for(p=0,i=len-j;i<len;i++) y[p++]=i;
			for(i=0;i<len;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

			for(i=0;i<len;i++) wv[i]=x[y[i]];
			for(i=0;i<m;i++) ws[i]=0;
			for(i=0;i<len;i++) ws[wv[i]]++;
			for(i=1;i<m;i++) ws[i]+=ws[i-1];
			for(i=len-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

			swap(x,y);
			for(i=1,p=1,x[sa[0]]=0;i<len;i++)
				x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
		}
	}
	void Build_H(char *r,const int &len)
	{
		int i,k=0;
		for(i=1;i<=len;i++) rank[sa[i]]=i;
		for(i=0;i<len;height[rank[i++]]=k)
			for(k?k--:0;r[i+k]==r[sa[rank[i]-1]+k];k++);
	}
};
class RMQ  //st
{
private:
	int LOG[Maxn];
	int POW[20];
	int dp[Maxn][20];
public:
	RMQ()
	{
		for(int i=0,l=1;i<20;i++,l*=2) POW[i]=l;
		LOG[0]=-2147483647;
		int cur=0,Next=1;
		for(int i=1;i<Maxn;i++)
		{
			if(i==POW[Next]) cur++,Next++;
			LOG[i]=cur;
		}
	}
	void Build(int *d,const int &len)
	{
		memset(dp,127,sizeof dp);
		for(int i=0;i<=len;i++) dp[i][0]=d[i];
		for(int i=1,l=2;l<=len+1;i++,l*=2)
			for(int j=0;j<=len;j++)
			{
				dp[j][i]=dp[j][i-1];
				if (j+l/2<=len) dp[j][i]=min(dp[j][i-1],dp[j+l/2][i-1]);
			}
	}
	int Query(int l,int r)
	{
		if(l>r) l^=r^=l^=r;
		return min(dp[l][LOG[r-l+1]],dp[r-POW[LOG[r-l+1]]+1][LOG[r-l+1]]);
	}
};
char str[Maxn+1],inv_str[Maxn+1];

int Readin()
{
	memset(str,0,sizeof str);
	memset(inv_str,0,sizeof inv_str);
	gets(str);
	int len=strlen(str);
	if(str[0]=='#') return EOF;
	for(int i=0;i<len;i++) inv_str[i]=str[len-1-i];
	return len;
}
Suffix_array s,inv_s;
RMQ S,rank_S,inv_S;
int start,_lenth;
bool BREAK(int &cases,int &lenth)
{
	lenth=Readin();
	if(lenth==EOF) return false;
	return true;
}

inline int Calculate(const int &p1,const int &p2,int *rank,RMQ &S)
{
	int pl=rank[p1],pr=rank[p2];
	if(pl<pr) pl++;
	else pr++;
	return S.Query(pl,pr);
}
int main()
{
	int lenth;
	int cases=1;
	int Maxtimes=1,L=1,p;

	while(BREAK(cases,lenth))
	{
		Maxtimes=1;
		L=1;
		p=0;
		printf("Case %d: ",cases++);
		s.Build_Sa(str,lenth);
		s.Build_H(str,lenth);
		S.Build(s.height,lenth);
		inv_s.Build_Sa(inv_str,lenth);
		inv_s.Build_H(inv_str,lenth);
		rank_S.Build(s.rank,lenth-1);
		inv_S.Build(inv_s.height,lenth);
		for(int l=1;l<lenth;l++)
		{
			for(int i=0;i+l<lenth;i+=l)
			{
				int tmp,times,left,right,tmp2;
				tmp=Calculate(i,i+l,s.rank,S);
				tmp2=Calculate(lenth-1-i,lenth-1-i-l,inv_s.rank,inv_S);
				times=tmp/l+1;
				left=max(0,i-(l-tmp%l));
				if(times<Maxtimes-1 || (times==Maxtimes-1 && Calculate(left,left+l,s.rank,S)<l) || left==i) continue;
				if(Calculate(left,left+l,s.rank,S)>=l && left!=i)
				{
					times++;
					//i-tmp+1~left
					tmp=s.sa[rank_S.Query(i-tmp2+1,left)];
				}
				else tmp=s.sa[rank_S.Query(i-tmp2+1,i)];
				if(Maxtimes==times)
				{
					if(s.rank[tmp]<s.rank[start])
					{
						start=tmp;
						_lenth=l*Maxtimes;
					}
				}
				else 
				{
					start=tmp,Maxtimes=times;
					_lenth=l*Maxtimes;
				}
			}
		}
		if(Maxtimes==1)
		{
			char Min='z';
			for(int i=0;i<lenth;i++) Min=Min<str[i]?Min:str[i];
			printf("%c\n",Min);
		}
		else
		{
			for(int i=start;i<start+_lenth;i++) 
				printf("%c",str[i]);
			printf("\n");
		}
	}
	return 0;
}

• Re:NlogN方法 (16) icool123 2012-03-15 12:28:44
• 你的程序有bug!!! (42) icool123 2012-03-15 14:20:40
• RMQ维护字典序的区间极值！！ (25) C20181220 2020-01-17 20:10:25