4
15
2016
0

[BZOJ2105] 增强型LCP

因为修改的次数比较少,所以每次暴力重构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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 585

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com