双hash模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const pll mod = make_pair(1e9 + 7, 1e9 + 9);
const pll base = make_pair(10007, 10009);
const int maxn = 1e6 + 5;
const int maxm = 1e6;
char str[maxn];
pll fac[maxn];
map<pll, int> mp;
struct MHash {
    pll L[maxn], R[maxn];
    void init() { //初始化 
        fac[0].first = fac[0].second = 1;
        for (int i = 1; i <= maxm; i++) {
            fac[i].first = (fac[i - 1].first * base.first) % mod.first;
            fac[i].second = (fac[i - 1].second * base.second) % mod.second;
        } 
    }
    pll getHash(char *str) { //获取传入字符串hash值 
        pll hash = make_pair(0, 0);
        int len = strlen(str);
        for (int i = 0; i < len; i++) {
            hash.first = (hash.first * base.first + str[i]) % mod.first;
            hash.second = (hash.second * base.second + str[i]) % mod.second;
        }
        return hash;
    }
    void init(char *str) { //字符串的前缀hash和后缀hash 
        int len = strlen(str + 1);
        R[len + 1].first = 0; R[len + 1].second = 0;
        for (int i = 1; i <= len; i++) {
            L[i].first = (L[i - 1].first * base.first + str[i]) % mod.first;
            L[i].second = (L[i - 1].second * base.second + str[i]) % mod.second;
        }
        for (int  i = len; i >= 1; i--) {
            R[i].first = (R[i + 1].first * base.first + str[i]) % mod.first;
            R[i].second = (R[i + 1].second * base.second + str[i]) % mod.second;
        }
    }
    pll getLHash(int l, int r) { //前缀区间hash值 
        pll hash;
        hash.first = ((L[r].first - L[l - 1].first * fac[r - l + 1].first) % mod.first + mod.first) % mod.first;
        hash.second = ((L[r].second - L[l - 1].second * fac[r - l + 1].second) % mod.second + mod.second) % mod.second;
        return hash;
    }
    pll getRHash(int l, int r) { //后缀区间hash值 
        pll hash;
        hash.first = ((R[l].first - R[r + 1].first * fac[r - l + 1].first) % mod.first + mod.first) % mod.first;
        hash.second = ((R[l].second - R[r + 1].second * fac[r - l + 1].second) % mod.second + mod.second) % mod.second;
        return hash;
    }
}mhash;


bool check(char *str) {
    int len = strlen(str);
    pll hash = mhash.getHash(str);
    pll tmp;
    for (int i = 0; i < len; i++) {
        for (int j = 'a'; j <= 'c'; j++) {
            if (j == str[i]) continue;
            tmp.first = (((j - str[i]) * fac[len - i - 1].first + hash.first) % mod.first + mod.first) % mod.first;
            tmp.second = (((j - str[i]) * fac[len - i - 1].second + hash.second) % mod.second + mod.second) % mod.second;    
            if (mp[tmp]) {
                return true;
            }
        }
    }
    return false;
}


int main() {
    int n, m;
    mhash.init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str); 
        mp[mhash.getHash(str)] = 1;
    }
    while (m--) {
        scanf("%s", str);
        if (check(str)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}