火星人 【问题描述】： 火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号： 序号 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。 比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速算法，但不甘心认输的地球人又给火星
人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。 具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。 【输入文件】 第一行给出初始的字符串。 第二行是一个非负整数M，表示操作的个数。 接下来的M行，每行描述一个操作。操作有3种，如下所示： 1.询 问。 语法：Q x y，x, y均为正整数。 功能：计算LCQ(x, y) 限制：1 <= x, y <= 当前字符串长度。 2 .修 改。 语法：R x d，x是正整数，d是字符。 功能：将字符串中第x个数修改为字符d。 限制：x不超过当前字符串长度。 3.插 入： 语法：I x d，x是非负整数，d是字符。 功能：在字符串第x个字符之后插入字符d，如果x = 0，则在字符串开头插入。
限制：x不超过当前字符串长度。
因为本弱不会后缀数组（后来知道这个题还不能用后缀数组做），就想用字符串hash来解决这个问题。
因为要维护插入和删除操作，所以我们维护一棵Splay，每个节点保存的是以当前节点为根的字符串的hash值。
寻找lcq的时候，直接二分答案就行了。
#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int maxn=1110000;const int c=13331;struct Node{ char a; int hash,size; Node *ch[2],*fa;}Edge[maxn];Node *Cnt1=&Edge[0];int m,Size,Hp[maxn];Node *New_Node(char a){ Node *p=++Cnt1; p->a=a; p->hash=Hp[0]*a; p->ch[0]=p->ch[1]=p->fa=NULL; p->size=1; return p;}Node *Root;char Data[maxn];void Update(Node *x){ if(x==NULL) return ; x->size=(x->ch[0]!=NULL?x->ch[0]->size:0)+(x->ch[1]!=NULL?x->ch[1]->size:0)+1; int S=x->size; //int L=(x->ch[0]!=NULL?x->ch[0]->size:0); int s0=x->ch[0]!=NULL?x->ch[0]->hash:0,s1=x->ch[1]!=NULL?x->ch[1]->hash:0; int len0=x->ch[0]!=NULL?x->ch[0]->size:0,len1=(x->ch[1]!=NULL?x->ch[1]->size:0); x->hash=s0*Hp[S-len0]+x->a*Hp[len1]+s1;}void Rotate(Node *x,int d){ Node *y=x->fa; x->fa->ch[d^1]=x->ch[d]; x->fa=y->fa; if(x->ch[d]!=NULL) x->ch[d]->fa=y; if(y->fa!=NULL) y->fa->ch[y==y->fa->ch[1]]=x; y->fa=x; x->ch[d]=y; if(y==Root) Root=x; Update(y); Update(x);}void Splay(Node *x,Node *rt){ if(x==NULL) return ; while(x->fa!=rt){ Node *y=x->fa; Node *z=y->fa; if(z==rt){ if(x==y->ch[0]) Rotate(x,1); else Rotate(x,0); } else{ if(z->ch[0]==y){ if(x==y->ch[0]){ Rotate(y,1); Rotate(x,1); } else { Rotate(x,0); Rotate(x,1); } } else{ if(y->ch[1]==x){ Rotate(y,0); Rotate(x,0); } else{ Rotate(x,1); Rotate(x,0); } } } } Update(x);}Node *Build(int L,int R,Node *&Fa){ if(L>R) return NULL; int Mid=(L+R)>>1; Node *o=New_Node(Data[Mid]); o->ch[0]=Build(L,Mid-1,o); o->ch[1]=Build(Mid+1,R,o); o->fa=Fa; Update(o); return o;}Node *Kth(Node *o,int k){ if(o==NULL) return o; if((o->ch[0]!=NULL?o->ch[0]->size:0)>=k) return Kth(o->ch[0],k); k=k-(o->ch[0]!=NULL?o->ch[0]->size:0); if(k<=1) return o; return Kth(o->ch[1],k-1);}void _Insert(int x,char a){ Node *K=Kth(Root,x); Splay(K,NULL); Node *K1=Kth(Root,x+1); Splay(K1,Root); Node *o=New_Node(a); if(Root->ch[1]!=NULL){ Root->ch[1]->ch[0]=o; o->fa=Root->ch[1]; Update(Root->ch[1]); Update(Root); } else{ Root->ch[1]=o; o->fa=Root; Update(o); Update(Root); }}void Modify(int x,char d){ Node *K=Kth(Root,x); Splay(K,NULL); Root->a=d; Update(Root);}int RK(int L,int R){ if(L>1&&R<Size){ Node *L1=Kth(Root,L-1); Splay(L1,NULL); Node *R1=Kth(Root,R+1); Splay(R1,Root); return Root->ch[1]->ch[0]->hash; } if(L==1&&R<Size){ Node *R1=Kth(Root,R+1); Splay(R1,NULL); return Root->ch[0]->hash; } if(L>1&&R==Size){ Node *L1=Kth(Root,L-1); Splay(L1,NULL); return Root->ch[1]->hash; } if(L==1&&R==Size){ return Root->hash; } return 0;}bool Check(int Ans,int x,int y){ int wdy1=RK(x,x+Ans-1); int wdy2=RK(y,y+Ans-1); if(wdy1==wdy2) return 1; else return 0;}void Query(int x,int y){ int r=Size-y+1,l=0; while(l<r){ int mid=(l+r+1)>>1; if(Check(mid,x,y)) l=mid; else r=mid-1; } printf("%d\n",r);}int main(){ //freopen("wdy.in","r",stdin); scanf("%s",&Data[1]); Size=strlen(Data+1); Hp[0]=1; for(int i=1;i<maxn;i++) Hp[i]=Hp[i-1]*c; Root=Build(1,Size,Root); scanf("%d",&m); for(int i=1;i<=m;i++){ char Cmd[10],d; int x,y; scanf("%s",&Cmd[1]); if(Cmd[1]=='Q'){ scanf("%d%d",&x,&y); //printf("%d:",i); Query(x,y); } if(Cmd[1]=='R'){ scanf("%d %c",&x,&d); Modify(x,d); } if(Cmd[1]=='I'){ scanf("%d %c",&x,&d); _Insert(x,d); Size++; } //printf("%d: \n",i); } return 0;}
转载于:https://www.cnblogs.com/Return-0/archive/2013/03/18/2966778.html
相关资源：数据结构—成绩单生成器