暴力 string 维护即可。

时间复杂度：$O(nm)$（大概是 1e10 的计算量，但远远达不到）。

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	cin>>s;
	int m;scanf("%d",&m);
	while(m--){
		char op[10],ch[10];int x,y;
		scanf("%s",op+1);
		if(op[1]=='Q'){
			scanf("%d%d",&x,&y);
			int cnt=0;
			for(int i=x-1,j=y-1;s[i]&&s[j]&&(s[i]==s[j]);i++,j++){
				cnt++;
			}
			printf("%d\n",cnt);
		}
		if(op[1]=='R'){
			scanf("%d%s",&x,ch+1);
			s[x-1]=ch[1];
		}
		if(op[1]=='I'){
			scanf("%d%s",&x,ch+1);
			s.insert(s.begin()+(x-1)+1,ch[1]);
		}
	}
	return 0;
}

平衡树维护区间哈希值。

时间复杂度：$O(m \log n)$。

#include<bits/stdc++.h>
#define fa(x) tr[x].fa
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
using namespace std;
typedef unsigned long long ULL;
const int N=2e5+5;
const ULL Hash=131;
const int inf=0x3f3f3f3f;
char str[N];int n;
ULL p[N];
void init(){
	p[0]=1;
	for(int i=1;i<=N-5;i++){
		p[i]=p[i-1]*Hash;
	}
}
struct trnode{
	int val,siz,fa,ch[2];
	ULL hash;
}tr[N];
int root,trlen;
void pushup(int x){
	if(!x)return;
	tr[x].siz=(tr[lc(x)].siz+tr[rc(x)].siz+1);
	tr[x].hash=tr[lc(x)].hash+tr[x].val*p[tr[lc(x)].siz]+tr[rc(x)].hash*p[tr[lc(x)].siz+1];
}
void add(int d,int fa){
	trlen++;int now=trlen;
	tr[now]={d,1,fa,0,0,(ULL)d};
	tr[fa].ch[1]=now;
	if(!fa)root=now;
}
void rotate(int x){
	int y=fa(x),z=fa(y);
	int w=(rc(y)==x),v=tr[x].ch[1-w];
	fa(v)=y,tr[y].ch[w]=v;
	fa(y)=x,tr[x].ch[1-w]=y;
	fa(x)=z,tr[z].ch[rc(z)==y]=x;
	pushup(y),pushup(x);
}
void splay(int x,int rt){
	while(fa(x)!=rt){
		int y=fa(x),z=fa(y);
		if(z!=rt){
			if((rc(z)==y)==(rc(y)==x))
				rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(!rt)root=x;
}
int find(int k){
	int x=root;
	while(1){
		if(tr[lc(x)].siz>=k){
			x=lc(x);
		}
		else if(tr[lc(x)].siz+1<k){
			k=k-tr[lc(x)].siz-1;
			x=rc(x);
		}
		else{
			return x;
		}
	}
}
int check(int l,int r){
	int x=find(l-1),y=find(r+1);
	splay(y,0),splay(x,y);
	return tr[rc(x)].hash;
}
int query(int x,int y){
	int l=0,r=n-y+1,ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(x,x+mid-1)==check(y,y+mid-1)){
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	return ans;
}
void change(int l,int c){
	int x=find(l);
	splay(x,0);
	tr[x].val=c;
}
void insert(int l,int c){
	int x=find(l),y=find(l+1);
	splay(y,0),splay(x,y);
	add(c,x);
	splay(trlen,0);
}
int main(){
	init();
	scanf("%s",str+1);
	n=strlen(str+1);
	add(-inf,0);
	for(int i=1;i<=n;i++){
		add(str[i]-'a',i);
		splay(trlen,0);
	}
	add(inf,n+1);
	splay(trlen,0);
	n++;
	int m;scanf("%d",&m);
	for(int i=1;i<=m;i++){
		char op[10],ch[10];int x,y;
		scanf("%s",op+1);
		if(op[1]=='Q'){
			scanf("%d%d",&x,&y);
			x++,y++;
			if(x>y)swap(x,y);
			printf("%d\n",query(x,y));
		}
		if(op[1]=='R'){
			scanf("%d%s",&x,ch+1);
			x++;
			change(x,ch[1]-'a');
		}
		if(op[1]=='I'){
			scanf("%d%s",&x,ch+1);
			x++;
			insert(x,ch[1]-'a');
			n++;
		}
	}
	return 0;
}