> #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;
> }

• 一种诡异的三分法 (0) frkstyc 2006-03-09 23:12:02