本題使用字符串的Hash來解決。將一個字符串看成是一個P進制的數字，那麼可以知道每一個字符串都可以被唯一表示(P> 256, 並不考慮高精度)。可是由於字符串的長度比較大，那麼我們無法保存如此大的數字。於是使用Hash mod2^64來作為Hash.(的卻可能會沖突，可是沖突的概率趨於無窮小)
然後就是Hash(s,P) = s[0]*P^(Len-1) + s[1] *P^(Len -2) + … + s[Len-1]*P^0 (mod2^64)
P隨便選個素數什麼的都可以。
之後假設沒有修改操作，那麼我們可以與處理出H[i]表示S[0..i]的Hash
那麼為了獲得S[l..r]的Hash,我們有:
S[0..r]= s[0]*P^r + s[1]*P^(r-1) +…+s[r]*P^0
S[0..l-1]=s[0]*P^(l-1)+s[1]*P^(l-2)+…+s[l-1]*P^0
於是
S[l..r]=s[l]*P^(r-l)+s[l+1]*P^(r-l-1)+…+s[r]*P^0
=S[0..r] – S[0..l-1]*P^(r-l+1)
=H[r] – H[l-1]*P^(r-l+1)
其中P^(r-l+1)顯然直接預處理。
於是查詢就可以O(1)
現在需要修改某些字符！
於是可以使用一顆線段樹來維護
[L..R]維護S[L..R]的Hash，這樣更新查詢均解決。更新和查詢均為O(logN)級別
[cpp]
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 100010
#define p 33
using namespace std;
typedef unsigned long long ll;
struct Tree{
int l,r;
ll hashes;
}tree[300000];
char str[2000100];
ll hh[maxn];
void init(){
int i;
hh[0]=1;
for(i=1;i<=maxn;i++)
hh[i]=hh[i-1]*p;
}
ll calhash(){
int i,len=strlen(str);
ll sum=0;
for(i=0;i<len;i++)
sum=sum*p+str[i]-'a'+1;
return sum;
}
void build(int s,int t,int id){
tree[id].l=s;tree[id].r=t;
if(s==t){
tree[id].hashes=str[s]-'a'+1;
return;
}
int mid=(s+t)>>1;
build(s,mid,id<<1);
build(mid+1,t,id<<1|1);
tree[id].hashes=tree[id<<1].hashes*hh[t-mid]+tree[id<<1|1].hashes;
}
void update(int l,int id){
if(tree[id].l==tree[id].r){
tree[id].hashes=str[l]-'a'+1;
return ;
}
int mid=(tree[id].l+tree[id].r)>>1;
if(l<=mid) update(l,id<<1);
else update(l,id<<1|1);
tree[id].hashes=tree[id<<1].hashes*hh[tree[id].r-mid]+tree[id<<1|1].hashes;
}
ll query(int s,int t,int id){
if(tree[id].l==s && tree[id].r==t)
return tree[id].hashes;
int mid=(tree[id].l+tree[id].r)>>1;
if(t<=mid) return query(s,t,id<<1);
else if(s>mid) return query(s,t,id<<1|1);
return query(s,mid,id<<1)*hh[t-mid]+query(mid+1,t,id<<1|1);
}
int main(){
int t,T,pos,l,r,i,q,n;
char s1[10],s2[10];
map<ll,int>mp;
init();
scanf("%d",&T);
for(t=1;t<=T;t++){
printf("Case #%d:\n",t);
scanf("%d",&n);
mp.clear();
for(i=1;i<=n;i++){
scanf("%s",str);
mp.insert(make_pair(calhash(),1));
}
scanf("%s",str);
int len=strlen(str);
build(0,len-1,1);
scanf("%d",&q);
for(i=1;i<=q;i++){
scanf("%s",s1);
if(s1[0]=='C'){
scanf("%d%s",&pos,s2);
str[pos]=s2[0];
update(pos,1);
}
else{
scanf("%d %d",&l,&r);
if(mp.find(query(l,r,1))!=mp.end()) printf("Yes\n");
else printf("No\n");
}
}
}
}
