CodeForces - 514C Watto and Mechanism

第一次写双模数哈希，感觉自己好弱智啊。

每次输入一个串，就枚举其每一位可能取的其他的字母（字母一共只有三种），根据原串哈希值推出现在的哈希，再插入\(set\)里面，最后再判断是否出现就行了。

详见代码。（有注释）

#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long ll;

const ll mod[2] = {(ll)(1e9 + 7), (ll)(1e9 + 9)};
const int N = 6e5 + 10;

int len, n, m;
char s[N];
ll f[N][2];
set < pair <ll, ll> > q;

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) > '9' || s < '0') {
        if(s == '-') f = -1;
        if(s == EOF) exit(0);
    }
    while(s >= '0' && s <= '9') {
        x = (x << 1) + (x << 3) + (s ^ 48);
        s = getchar();
    }
    return x * f;
}

void init() {//预处理每一位的单位值
    f[0][0] = f[0][1] = 1;
    for(int i = 1; i <= 6e5; ++ i)
        for(int j = 0; j < 2; ++ j)
            f[i][j] = f[i - 1][j] * 3 % mod[j]; 
}

ll hash(const int op) {
    ll res = 0;
    for(int i = 0; i < len; ++ i)
        res = (res * 3 + s[i] - 'a') % mod[op];
    return res;
}

int main() {
    ll h1, h2;
    init();
    n = read(), m = read();
    for(int i = 1; i <= n; ++ i) {
        scanf("%s", s); len = strlen(s);
        h1 = hash(0), h2 = hash(1);
        for(int j = 0; j < len; ++ j)
            for(int k = 'a'; k <= 'c'; ++ k)
                if(k != s[j])//前面的位在哈希的过程中不断乘上base会变大，故f[len - j + 1]反而是对应位的单位
                    q.insert(make_pair((h1 + f[len - j - 1][0] * (k - s[j]) + mod[0] * 3) % mod[0], (h2 + f[len - j - 1][1] * (k - s[j]) + mod[1] * 3) % mod[1]));
    }
    for(int i = 1; i <= m; ++ i) {
        scanf("%s", s); len = strlen(s);
        puts(q.count(make_pair(hash(0), hash(1))) ? "YES" : "NO");
    }
    return 0;
}

最后再附一篇用trie树做的做法。-->右转-->

CodeForces - 514C Watto and Mechanism

原文：https://www.cnblogs.com/AWhiteWall/p/12334684.html