题解：
首先肯定不是后缀数组，当然splay比后缀数组要简单一些。
求解这个问题，我们可以二分，对于两个串A，B他们的最长公共前缀是可以二分出来的。
那么我们对于每一个后缀，二分一下，但是需要维护这一个东西，那么我们使用splay来维护序列。按照下标为关键字来把初始字符串构造成一棵splay，然后维护一个Hash值代表子树的字符串的Hash值。每次将L-1旋转到根，再把R+1旋转到根的右儿子，这样就可以查询一段区间的Hash值了。
?1 #include<cstdio> ?2 #include<cstring> ?3 #include<iostream> ?4 #include<algorithm> ?5 #define LL long long ?6 using namespace std; ?7 const int MAXN=160000,mod=192608173; ?8 char s[MAXN]; ?9 int n,m,root,CNT; 10 int v[MAXN]; 11 int sz[MAXN],fa[MAXN],ha[MAXN],val[MAXN],ch[MAXN][2]; 12 void Update(int x) 13 { 14 ??int ls=ch[x][0],rs=ch[x][1]; 15 ??sz[x]=sz[ls]+sz[rs]+1; 16 ??ha[x]=ha[ls]+(LL)val[x]*v[sz[ls]]%mod+(LL)ha[rs]*v[sz[ls]+1]%mod; 17 ??ha[x]%=mod; 18 } 19 void Rotate(int x,int &y) 20 { 21 ??int old=fa[x],oldf=fa[old],op=ch[old][1]==x; 22 ??if(old==y) y=x; 23 ??else ch[oldf][ch[oldf][1]==old]=x; 24 ??fa[x]=oldf; 25 ??fa[ch[x][op^1]]=old; ch[old][op]=ch[x][op^1]; 26 ??fa[old]=x; ch[x][op^1]=old; 27 ??Update(old); Update(x); 28 } 29 void Splay(int x,int &y) 30 { 31 ??int old,oldf; 32 ??while(x!=y) 33 ????{ 34 ??????old=fa[x]; oldf=fa[old]; 35 ??????if(old!=y){ 36 ????????if((ch[old][0]==x)^(ch[oldf][0]==old)) Rotate(x,y); 37 ????????else Rotate(old,y); 38 ??????} 39 ??????Rotate(x,y); 40 ????} 41 } 42 void Build(int &x,int ll,int rr,int FA) 43 { 44 ??x=++CNT; int mid=(ll+rr)/2; 45 ??fa[x]=FA; val[x]=s[mid]-‘a‘+1; 46 ??if(ll<mid)Build(ch[x][0],ll,mid-1,x); 47 ??if(rr>mid)Build(ch[x][1],mid+1,rr,x); 48 ??Update(x); 49 } 50 int find(int x) 51 { 52 ??int now=root; 53 ??while(1) 54 ????{ 55 ??????if(x<=sz[ch[now][0]]) now=ch[now][0]; 56 ??????else 57 ????????{ 58 ??????????int tmp=sz[ch[now][0]]+1; 59 ??????????if(x<=tmp) return now; 60 ??????????x-=tmp; now=ch[now][1]; 61 ????????} 62 ????} 63 } 64 int Query(int ll,int rr) 65 { 66 ??int x=find(ll-1),y=find(rr+1); 67 ??Splay(x,root); Splay(y,ch[root][1]); 68 ??return ha[ch[y][0]]; 69 } 70 int work(int x,int y) 71 { 72 ??int L=1,R=n-y,mid,res=0; 73 ??while(L<=R) 74 ????{ 75 ??????mid=(L+R)/2; 76 ??????if(Query(x,x+mid-1)==Query(y,y+mid-1)) L=mid+1 ,res=mid; 77 ??????else R=mid-1; 78 ????} 79 ??return res; 80 } 81 void Insert(int x,int V) 82 { 83 ??int y=x+1; n++; 84 ??x=find(x); y=find(y); 85 ??Splay(x,root); Splay(y,ch[root][1]); 86 ??CNT++; val[CNT]=V; 87 ??fa[CNT]=y; ch[y][0]=CNT; 88 ??Update(CNT); Update(y); Update(root); 89 } 90 int main() 91 { 92 ??scanf("%s",s+2); s[1]=‘a‘-1; 93 ??n=strlen(s+1)+1; s[n]=‘a‘-1; 94 ??scanf("%d",&m); v[0]=1; 95 ??for(int i=1;i<MAXN;i++)v[i]=(LL)v[i-1]*27%mod; 96 ??Build(root,1,n,0); 97 ??while(m--) 98 ????{ 99 ??????scanf("%s",s);100 ??????if(s[0]==‘Q‘)101 ????????{102 ??????????int x,y; scanf("%d%d",&x,&y);103 ??????????if(x>y) swap(x,y);104 ??????????printf("%d\n",work(x+1,y+1));105 ????????}106 ??????else if(s[0]==‘R‘)107 ????????{108 ??????????int x; scanf("%d%s",&x,s);109 ??????????x=find(x+1); Splay(x,root); 110 ??????????val[x]=s[0]-‘a‘+1; Update(x);111 ????????}112 ??????else if(s[0]==‘I‘)113 ????????{114 ??????????int x; scanf("%d%s",&x,s); 115 ??????????Insert(x+1,s[0]-‘a‘+1);116 ????????}117 ????}118 }[JSOI2008]火星人
原文地址：http://www.cnblogs.com/D-O-Time/p/8081634.html