hdu 3973 字符串hash+线段树 - c++编程基础

Problem Description You are given some words {Wi}. Then our stupid AC will give you a very long string S. AC is stupid and always wants to know whether one substring from S exists in the given words {Wi} .

For example, S = abcd, and the given words {Wi} = {bc, ad, dd}. Then Only S[2..3] = bc exists in the given words. (In this problem, the first element of S has the index 0.)

However, this is toooooooooooo easy for acmers ! The stupid and evil AC will now change some letters in S. So could you solve this problem now?
Input The first line is one integer T indicates the number of the test cases. (T <=20)

Then for every case, there is one integer n in the first line indicates the number of the given words(The size of the {Wi}) . Then n lines has one string which only has 'a'- 'z'. (1 <= n <= 10000, sigma|Wi| <= 2000000) .

Then one line has one string S, here |S| <= 100000.

Then one integer m, indicating the number of operations. (1 <= m <= 100000)

Then m lines , each line is the operation:

(1)Q L R , tell AC whether the S[L..R] exists in the given strings ;

(2)C X Y , chang S[X] to Y, here Y : 'a'-'z' .www.2cto.com
Output First output “Case #idx:” in a single line, here idx is the case number count from 1.Then for each Q operation, output Yes if S[L..R] exists in the given strings, otherwise output No.
Sample Input

1
2
ab 
ioc 
ipcad 
6 
Q 0 2 
Q 3 4 
C 1 o 
C 4 b 
Q 0 2 
Q 3 4

Sample Output

Case #1:
No
No 
Yes 
Yes

/**
hdu 3973  线段树单点更新区间求值+字符串hash
题目大意：给定多个字符串，然后给定一个大串，对该串进行单点更新和区间查询，查询的区间子串是不是在已知的字符串中出现
解题思路：对字符串进行hash处理采用线段树来进行更新，用set存放字符串的哈希值。至于怎么哈希和大白书上的思路差不多只是这里是表示的前缀
*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn=100010; const int seed=31; typedef unsigned long long LL; struct note { int l,r; LL hashes; }tree[maxn*4]; char str[2000100]; LL Hash[maxn]; int n; void init() { Hash[0]=1; for(int i=1;i
      
       >1; if(l<=mid) update(l,root<<1); else update(l,root<<1|1); tree[root].hashes=tree[root<<1].hashes*Hash[tree[root].r-mid]+tree[root<<1|1].hashes; } LL query(int l,int r,int root) { // printf(** ); if(tree[root].l==l&&tree[root].r==r) return tree[root].hashes; int mid=(tree[root].r+tree[root].l)>>1; if(r<=mid)return query(l,r,root<<1); else if(l>mid)return query(l,r,root<<1|1); return query(l,mid,root<<1)*Hash[r-mid]+query(mid+1,r,root<<1|1); } int main() { int T,tt=0; init(); scanf(%d,&T); while(T--) { printf(Case #%d: ,++tt); scanf(%d,&n); set
       
        mp; for(int i=0;i
        
         ?