首先我们可以用splay来维护这个字符串，那么对于某两个位置的lcp，维护每个节点的子树的hash，然后二分判断就好了。
/************************************************************** Problem: 1014 User: BLADEVIL Language: C++ Result: Accepted Time:4468 ms Memory:3640 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <cstring> #include <algorithm> #define maxn 100010 using namespace std; char s[maxn]; int fac[maxn],key[maxn],num,rot,son[maxn][2],father[maxn],size[maxn],hash[maxn]; void update(int x) { if (!x) return ; hash[x]=hash[son[x][0]]+(key[x]+hash[son[x][1]]*27)*fac[size[son[x][0]]]; size[x]=size[son[x][0]]+size[son[x][1]]+1; } int build(int l,int r) { int mid=l+r>>1,left=0,right=0; if (mid<r) right=build(mid+1,r); if (mid>l) left=build(l,mid-1); father[left]=father[right]=mid; son[mid][0]=left; son[mid][1]=right; update(mid); return mid; } void rotate(int x,int &rot) { int y=father[x],z=father[y]; int p=(son[y][1]==x),q=p^1; if (y==rot) rot=x; else if (son[z][0]==y) son[z][0]=x; else son[z][1]=x; father[x]=z; father[y]=x; father[son[x][q]]=y; son[y][p]=son[x][q]; son[x][q]=y; update(y); } void splay(int x,int &rot) { while (x!=rot) { int y=father[x],z=father[y]; if (y!=rot) if ((son[y][0]==x)^(son[z][0]==y)) rotate(x,rot); else rotate(y,rot); rotate(x,rot); } update(x); } int find(int x) { int t=rot; while (1) { if (size[son[t][0]]+1==x) return t; else if (size[son[t][0]]+1>x) t=son[t][0]; else if (size[son[t][0]]+1<x) x-=size[son[t][0]]+1,t=son[t][1]; } } bool judge(int x,int y,int len) { if (len==1) return key[find(x+1)]==key[find(y+1)]; int p=find(x),q=find(x+len+1); splay(p,rot); splay(q,son[rot][1]); int a1=hash[son[q][0]]; p=find(y); q=find(y+len+1); splay(p,rot); splay(q,son[rot][1]); int a2=hash[son[q][0]]; return a1==a2; } int main() { scanf("%s",&s); num=strlen(s); fac[0]=1; for (int i=1;i<maxn;i++) fac[i]=fac[i-1]*27; for (int i=2;i<=num+1;i++) key[i]=s[i-2]-'a'+1; num+=2; rot=build(1,num); int task; scanf("%d",&task); while (task--) { int x,y; scanf("%s",&s); if (s[0]=='Q') { scanf("%d%d",&x,&y); if (x>y) swap(x,y); int l=1,r=num-y-1,mid,ans=0; while (l<=r) { mid=l+r>>1; if (judge(x,y,mid)) ans=mid, l=mid+1; else r=mid-1; } printf("%d ",ans); } else if (s[0]=='R') { scanf("%d%s",&x,&s); int p=find(x+1); key[p]=s[0]-'a'+1; splay(p,rot); } else if (s[0]=='I') { scanf("%d%s",&x,&s); key[++num]=s[0]-'a'+1; int p=find(x+1); splay(p,rot); int q=find(x+2); splay(q,son[rot][1]); father[num]=q; son[q][0]=num; splay(num,rot); } } return 0; }