题目链接：http://icpc.njust.edu.cn/Problem/Hdu/3973/
题意是：给出一个模式串，再给出一些串组成一个集合，操作分为两种，一种是替换模式串中的一个字符，还有一种是查询模式串中[l,r]区间的字符串有没有出现在字符串集合中。
由于数据量很大，只能用O(nlogn)复杂度的算法才能通过，我们首先想到区间查询的操作线段树是可以做的，但是怎么样将一个子串唯一化呢？这就要说道字符串哈希了，我的做法是通过字符串哈希将字符串变成31进制数并且让它自然溢出，也就是对2^64取模。然后我们想到如何合并左右子区间呢？根据哈希的思想我们很容易想到：如果右区间的hash值为hash1，左区间的hash值为hash2，右区间的长度是len，则合并之后的hash=hash2*31^len+hash1，根据这样的策略可以知道任何区间的子串的hash值。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define pb(i) push_back(i)
#define ppb(x) pop_back(x)
#define inf 0x3f3f3f3f
#define maxn 100010
#define maxm 2000005
int n,m,x,y;
ll pp=;
ll t[maxn<<],p[maxm];
char s[maxm],a[maxm];
void init()
{
p[]=;
f(i,,maxm-)
{
p[i]=p[i-]*pp;
}
}
ll gethash(char* s)//获取字符串的哈希值
{
ll ans=;
f(i,,strlen(s)-)
{
ans=ans*pp+s[i]-'a'+;//哈希值自然溢出，也就是对2^64取模
}
return ans;
}
void pushup(int rt,int len)//传入根节点以及右子区间的长度
{
t[rt]=t[rt<<]*p[len]+t[rt<<|];
}
void build(int l,int r,int rt)
{
if(l==r)
{
t[rt]=a[l]-'a'+;
return;
}
int mid=l+r>>;
build(lson);
build(rson);
pushup(rt,r-mid);
}
void update(int l,int r,int rt,int pos,char C)
{
if(l==r)
{
t[rt]=C-'a'+;
return;
}
int mid=l+r>>;
if(pos<=mid)update(lson,pos,C);
else update(rson,pos,C);
pushup(rt,r-mid);
}
ll query(int l,int r,int rt,int L,int R)
{
if(l>=L&&r<=R)//只有区间完全重合的时候取出hash值时不需要另加操作
{
return t[rt];
}
int mid=l+r>>;
if(R<=mid) return query(lson,L,R);//分成三种情况，因为合并的时候需要乘系数
else if(L>mid) return query(rson,L,R);
return query(lson,L,mid)*p[R-mid]+query(rson,mid+,R);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
int tt;
scan(tt);
init();
f(kk,,tt)
{
set<ll> map;//字符串到hash值的映射表
scan(n);
f(i,,n)
{
scanf("%s",s);
map.insert(gethash(s));
}
scanf("%s",a+);
int len=strlen(a+);
build(,len,);
scan(m);
char q[];
pf("Case #%d:\n",kk);
while(m--)
{ scanf(" %s",q);
if(q[]=='Q')
{
scan(x);
scan(y);
x++;//注意代码中线段树的左端点是从1开始的
y++;
// dbg(query(1,len,1,x,y));
if(map.find(query(,len,,x,y))!=map.end())
pf("Yes\n");
else pf("No\n");
}
else if(q[]=='C')
{
char str[];
scan(x);
x++;
scanf("%s",str);
update(,len,,x,str[]);
}
}
}
}