因为修改的次数比较少，所以每次暴力重构hash就可以了
LCP可以用二分来做
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const unsigned long long Mod1=131ll,Mod2=171ll;
int n,q;
string s;
char ch[1000005];
unsigned long long hash1[1000005],hash2[1000005],Pow1[1000005],Pow2[1000005];
void MakeHash(){
n=s.length();
hash1[n-1]=s[n-1];
hash2[n-1]=s[n-1];
for(int i=n-2;i>=0;i--){
hash1[i]=hash1[i+1]*Mod1+s[i];
hash2[i]=hash2[i+1]*Mod2+s[i];
}
}
void Prepare(){
Pow1[0]=1ll;
Pow2[0]=1ll;
for(int i=1;i<=1000000;i++){
Pow1[i]=Pow1[i-1]*Mod1;
Pow2[i]=Pow2[i-1]*Mod2;
}
}
pair<unsigned long long,unsigned long long> GetHash(int l,int len){
return make_pair(hash1[l]-hash1[l+len]*Pow1[len],hash2[l]-hash2[l+len]*Pow2[len]);
}
int LCP(int a,int b){
if(a>b)swap(a,b);
int l=0,r=n-b;
while(l<=r){
int mid=l+r>>1;
if(GetHash(a,mid)!=GetHash(b,mid))r=mid-1;
else l=mid+1;
}
return r;
}
int main(){
freopen("2105.in","r",stdin);
freopen("2105.out","w",stdout);
scanf("%d %d",&n,&q);
scanf("%s",ch);s=ch;
Prepare();
MakeHash();
while(q--){
char opt[10];
scanf("%s",opt);
if(opt[0]=='L'){
int l,r;
scanf("%d %d",&l,&r);
l--;r--;
printf("%d\n",LCP(l,r));
}
if(opt[0]=='A'){
int x;
scanf("%d %s",&x,ch);
x--;
s.insert(x,ch);
MakeHash();
}
if(opt[0]=='C'){
int x,y;
scanf("%d %d %s",&x,&y,ch);
x--;y--;
for(int i=x;i<=y;i++)s[i]=ch[i-x];
MakeHash();
}
if(opt[0]=='D'){
int x,y;
scanf("%d %d",&x,&y);
x--;y--;
s.erase(x,y-x+1);
MakeHash();
}
}
return 0;
}
评论 (0)
