splay维护哈希值即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 100010
#define P 509
#define lson tree[k].ch[0]
#define rson tree[k].ch[1]
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int m,cnt,root;
ull p[N];
char s[N];
struct data{int ch[],fa,size,x;ull hash;
}tree[N];
void up(int k)
{
tree[k].size=tree[lson].size+tree[rson].size+;
tree[k].hash=tree[lson].hash*p[tree[rson].size+]+tree[k].x*p[tree[rson].size]+tree[rson].hash;
}
void build(int &k,int l,int r)
{
if (l>r) return;
int mid=l+r>>;
k=++cnt,tree[k].x=s[mid]-'a';
build(lson,l,mid-),build(rson,mid+,r);
tree[lson].fa=tree[rson].fa=k;
up(k);
}
int whichson(int k){return tree[tree[k].fa].ch[]==k;}
void move(int k)
{
int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k);
if (fa) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf;
tree[tree[k].ch[!p]].fa=fa,tree[fa].ch[p]=tree[k].ch[!p];
tree[k].ch[!p]=fa,tree[fa].fa=k;
up(fa),up(k);
}
void splay(int k,int rt)
{
while (tree[k].fa!=rt)
{
int fa=tree[k].fa;
if (tree[fa].fa!=rt)
if (whichson(k)^whichson(fa)) move(k);
else move(fa);
move(k);
}
if (!rt) root=k;
}
int find(int k,int x)
{
if (tree[lson].size+==x) return k;
if (tree[lson].size>=x) return find(lson,x);
else return find(rson,x-tree[lson].size-);
}
int split(int x,int y)
{
int p=find(root,x),q=find(root,y+);
splay(p,);
splay(q,p);
return q;
}
ull gethash(int x,int y)
{
int p=split(x,y);
return tree[tree[p].ch[]].hash;
}
void ins(int k,int x)
{
int p=split(k+,k);
k=++cnt;tree[k].fa=p,tree[p].ch[]=k,tree[k].x=x;
up(k),up(p),up(root);
}
void modify(int k,int x)
{
int p=split(k,k);
tree[k=tree[p].ch[]].x=x;
up(k),up(p),up(root);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1014.in","r",stdin);
freopen("bzoj1014.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
scanf("%s",s+);int n=strlen(s+);
p[]=;for (int i=;i<=;i++) p[i]=p[i-]*P;
build(root,,n+);
m=read();
while (m--)
{
char c=getc();
if (c=='Q')
{
int x=read(),y=read();
int l=,r=n-max(x,y)+,ans=;
while (l<=r)
{
int mid=l+r>>;
if (gethash(x,x+mid-)==gethash(y,y+mid-)) ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
if (c=='I')
{
n++;int x=read();char c=getc();
ins(x,c-'a');
}
if (c=='R')
{
int x=read();char c=getc();
modify(x,c-'a');
}
}
return ;
}