cf_514C(字符串哈希)

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121897#problem/G 

Watto and Mechanism

Time Limit:3000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit  Status

Description

Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: "Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs froms in exactly one position".

Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of n initial lines and m queries. He decided to entrust this job to you.

Input

The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·10⁵, 0 ≤ m ≤ 3·10⁵) — the number of the initial strings and the number of queries, respectively.

Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn't exceed 6·10⁵. Each line consists only of letters 'a', 'b', 'c'.

Output

For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).

Sample Input

Input

2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

Output

YES
NO
NO

题意：

给出n个字符串，再做m次询问，每次询问给你一条字符串，问你之前的n个字符串里是否存在和待查询串，有差别且仅差一个字符的字符串。有输出YES，没有NO

思路：

先算出N个字符串的哈希值，存进set。

每次查询时，算出待查询串的哈希值，遍历串上每一个位置，改变位置上字母，以产生差且仅差一个字符的新字符串，直接生成新字符串的哈希值。

注意生成新哈希值是可以根据原哈希值用O（1）方法算出，对于一个HASH值来说，你可以对它做除法以外的任何运算，不会影响HASH值的正确性，我之前对字符串哈希的理解是有偏颇的。HASH值被取模之后虽然失去了数学意义，但仍保持数学正确性，它的每一位并不再有意义，但是整体来讲，对其运算仍然是正确的。这题就很好的说明了这一点。

然后*说，MOD值要取得很大，WA了就去把MOD值改大！！注意改大的话用long long

 

 

字符串的hash主要是通过模拟字符串每一位对应到相应的数然后用相应进制去模拟加法即可

下面是代码：

#include <iostream>  
#include <cstdio>  
#include <cmath>  
#include <cstring>  
#include <set>  
using namespace std;  
typedef long long ll;  
const int maxn = 6*1e5 + 50;  
const ll MOD = 1e11 + 7;  
const int base = 3;  
  
char str[maxn];  
set<ll> mySet;  
ll key;  
ll p[maxn];  
  
ll getHash()  
{  
    ll num=0;  
    int len = strlen(str);  
    for(int i=len-1;i>=0;i--){  
        num = (num*base + str[i]-'a'+1) % MOD;  
    }  
    return num;  
}  
  
ll changeKey(ll key,int pos,int type)  
{  
    ll tkey = ((key - (str[pos]-'a'+1)*p[pos] ) % MOD + MOD + (type+1)*p[pos] ) % MOD;  
    return tkey;  
}  
  
int main()  
{  
    int i,j;  
    p[0] = 1;  
    for(i=1;i<maxn;i++){  
        p[i] = p[i-1]*base % MOD;  
    }  
    int n,m;  
    cin>>n>>m;  
    while(n--){  
        scanf("%s",str);  
        key = getHash();  
        mySet.insert(key);  
        //cout<<key<<endl;  
    }  
    while(m--){  
        scanf("%s",str);  
        key = getHash();  
        int len = strlen(str);  
        int found = 0;  
        for(i=0;i<len;i++){  
            if(found) break;  
            for(j=0;j<3;j++){  
                if(str[i]-'a' == j) continue;  
                ll tkey = changeKey(key,i,j);  
                //cout<<tkey<<endl;  
                if(mySet.find(tkey) != mySet.end()){  
                    cout<<"YES"<<endl;  
                    found = 1; break;  
  
                }  
            }  
        }  
        if(!found) cout<<"NO"<<endl;  
    }  
    return 0;  
}