#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <algorithm>
using namespace std;

#define M 51000
#define N 100000                //排序数组的大小

int K;
int SA[N][20];                   //后缀数组
int RANK[N][20];                 //名次数组
int h[N];                        //h[i]=height[RANK[i]]
int height[N];                   //height[i]=LCP(i-1,i)
int RMQ[N][20];                  //对height数组进行RMQ运算

int B[N];
int C[M];                        //计数数组
int LEN;

bool mark[N];
char S[N];                       //等处理字符串
char ori[N];
char buf[N];

int ins[N],ni;
int INS[N],NI;

//计算后缀数组SA与名次数组RANK

void SUFFIX_ARRAY_INIT(char *s)
{
	int i,j,OFFSET,p;
	for(K=0;;K++) if ((1<<K)>=LEN) break;
	
	//先对长为1的前缀进行排序,即对SA[][0]进行排序
	memset(C,0,sizeof(C));

	for(i=0;i<LEN;i++) C[s[i]]++;
	for(i=1;i<200;i++) C[i]+=C[i-1];
	for(i=LEN-1;i>=0;i--){
		C[s[i]]--;
		B[C[s[i]]]=i;
	}
	for(i=0;i<LEN;i++){
		SA[i][0]=B[i];
		if (i&&S[B[i]]==S[B[i-1]]) RANK[B[i]][0]=RANK[B[i-1]][0];
		else RANK[B[i]][0]=i;
	}

	OFFSET=1;
	for(j=1;j<=K;j++){
		printf("%d\n",clock());
		memset(C,0,sizeof(C));
		for(i=0;i<LEN;i++) C[RANK[i+OFFSET][j-1]]++;
		for(i=1;i<LEN;i++) C[i]+=C[i-1];
		for(i=LEN-1;i>=0;i--){
			C[RANK[i+OFFSET][j-1]]--;
			B[C[RANK[i+OFFSET][j-1]]]=i;
		}

		memset(C,0,sizeof(C));
		for(i=0;i<LEN;i++) C[RANK[B[i]][j-1]]++;
		for(i=1;i<LEN;i++) C[i]+=C[i-1];

		for(i=LEN-1;i>=0;i--){
			C[RANK[B[i]][j-1]]--;
			SA[C[RANK[B[i]][j-1]]][j]=B[i];
		}

		for(i=0;i<LEN;i++){
			if (i&&RANK[SA[i][j]+OFFSET][j-1]==RANK[SA[i-1][j]+OFFSET][j-1]
				&&RANK[SA[i][j]][j-1]==RANK[SA[i-1][j]][j-1])
				RANK[SA[i][j]][j]=RANK[SA[i-1][j]][j];
			else RANK[SA[i][j]][j]=i;
		}
		
		OFFSET<<=1;
	}
	
	height[0]=0;
	

	for(i=0;i<LEN;i++){
		if (RANK[i][K]==0) h[i]=0;
		else{
			if (i==0||h[i-1]<=1){
				for(p=0;;p++) if (s[i+p]!=s[SA[RANK[i][K]-1][K]+p]) break;
				h[i]=p;
			}
			else{
				for(p=h[i-1]-1;;p++) if (s[i+p]!=s[SA[RANK[i][K]-1][K]+p]) break;
				h[i]=p;
			}
		}
	}
	for(i=1;i<LEN;i++) height[i]=h[SA[i][K]];
}

void RMQ_INIT(int *height,int n)
{
	int K=0,i,j;
	while(((1<<(K+1)))<=n) K++;
	for(i=0;i<n;i++) RMQ[i][0]=height[i];
	for(j=1;j<=K;j++){
		for(i=0;i<=n-(1<<j);i++)
			RMQ[i][j]=
			RMQ[i][j-1]<RMQ[i+(1<<(j-1))][j-1]?RMQ[i][j-1]:RMQ[i+(1<<(j-1))][j-1];
	}
}

int lcp(int i,int j)
{
	int k=0;
	if (i==j) return LEN-1-SA[i][K];
	if (i>j) swap(i,j);
	i++;
	while((1<<(k+1))<=(j-i+1)) k++;
	return RMQ[i][k]<RMQ[j-(1<<k)+1][k]?RMQ[i][k]:RMQ[j-(1<<k)+1][k];
}

int query(int i,int j,int ii,int jj)
{
	int k,na,nb,len,ret,m,ti=0,tj;
	len=strlen(S);
	if (i==j){
		for(k=NI-1;k>=0;k--) if (INS[k]>i) ti++;else break;
		return LEN-1-i+ti;
	}
	na=nb=LEN-1;
	for(k=ii;k<NI;k++) if (INS[k]>i){
		na=INS[k];
		break;
	}
	ti=k;
	for(k=jj;k<NI;k++) if (INS[k]>j){
		nb=INS[k];
		break;
	}
	tj=k;
	ret=lcp(RANK[i][K],RANK[j][K]);
	m=na-i<nb-j?na-i:nb-j;
	if (ret<m) return ret;
	ret=m;
	i=i+m+ti;
	j=j+m+tj;
	for(;i<len&&j<len&&S[i]==S[j];i++,j++){
		if (!mark[i]&&!mark[j]) return ret+query(i-ti,j-tj,ti,tj);
		if (mark[i]) ti++;
		if (mark[j]) tj++;
		ret++;
	}
	return ret;
}

int main()
{
	int i,j,k,p,t,len;
	char c[2];
	freopen("input.dat","r",stdin);
	while(scanf("%s",S)!=EOF){
		strcpy(ori,S);
		LEN=strlen(S)+1;
		
		memset(RANK,0,sizeof(RANK));
		memset(mark,0,sizeof(mark));
		SUFFIX_ARRAY_INIT(S);
		
		//printf("%d\n",clock());
		RMQ_INIT(height,LEN);
		//printf("%d\n",clock());

		//return 0;
		NI=ni=0;
		scanf("%d",&k);
		while(k--){
			scanf("%s",c);
			switch(c[0]){
			case 'I':
				scanf("%s%d",c,&p);
				if (p>strlen(S)){
					S[strlen(S)+1]=0;
					S[strlen(S)]=c[0];
					ins[ni]=strlen(S)-1;
					mark[ins[ni]]=1;
					ni++;
					INS[NI++]=LEN-1;
				}
				else{
					strcpy(buf,S+p-1);
					S[p-1]=c[0];
					strcpy(S+p,buf);
					len=strlen(S);
					for(i=ni-1;i>=0;i--) 
						if (ins[i]>=p-1){
						
							ins[i+1]=ins[i]+1;
						
							mark[ins[i]]=0;
						
							mark[ins[i+1]]=1;
					
						}else break;

					ins[i+1]=p-1;
					mark[p-1]=1;
					ni++;
					t=0;
					for(i=0;i<ni;i++) if (ins[i]<p-1) t++;
					t=p-1-t;
					for(i=NI-1;i>=0;i--) 
						if (INS[i]>t)INS[i+1]=INS[i];
						else break;
					INS[i+1]=t;
					NI++;
				}
				break;
			case 'Q':
				scanf("%d%d",&i,&j);
				i--;j--;
				printf("%d\n",query(i,j,0,0));
				break;
			}
		}
	}
	return 0;
}

• 其实这个体的后缀数组基本上没发挥什么作用 (5014) frkstyc 2006-03-09 22:59:49
• 问题：怎么O(n)构造后缀数组？ (5014) sunmoonstar 2006-03-09 23:04:05
  • 一种诡异的三分法 (0) frkstyc 2006-03-09 23:12:02