题解 CF514C 【Watto and Mechanism】

Styx · 2018-11-02 07:43:37 · 题解

单模哈希就可以了

这种东西只要不被面向模数hack，随便取一个11-12位大质数应该就能过

具体做法就是把字典串都先hash掉扔到set里
然后对于输入串，每个串把每一位分别换成另外两个字母，计算新串的hash值并且在set里找是否插入过这个值，这个操作对于每个字母位复杂度是O(logn)的。

大质数就取23333333377之类的意思一下就可以了

代码如下：

#include<bits/stdc++.h>
#define mod 23333333377ll
using namespace std;

set<long long> ht;
int n,m;

string tmp;

long long get_hash(string x)
{
    int len=x.length();
    long long hash_val=0;
    for(int i=0;i<len;i++)
    {
        hash_val=(hash_val*4+1ll*(x[i]-'a'))%mod;
    }
    return hash_val;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        cin>>tmp;
        ht.insert(get_hash(tmp));
    }
    for(int i=1;i<=m;i++)
    {
        int flag=0;
        cin>>tmp;
        long long h=get_hash(tmp);
        int len=tmp.size();
        long long base=1;
        for(int j=len-1;j>=0;j--)
        {
            if(flag) break;
            for(int k=0;k<3;k++)
            {
                if(tmp[j]-'a'==k) continue;
                long long res=(h-(tmp[j]-'a')*base%mod+k*base%mod+mod)%mod;
                if(ht.count(res))
                {
                    flag=1;
                    break;
                }
            }
            base=base*4%mod;
        }
        if(flag) puts("YES");
        else puts("NO");
    }
}