给出n个已知字符串,m次询问,每次询问给出一个字符串,问上面n个字符串中是否有一个字符串满足恰好有一个字母不同于询问的字符串。(字符串的字符集为{'a','b','c'})n,m<=3e5,输入总长度不超过6e5。
注意:这里如果使用hash自动溢出会被卡掉,所以使用双hash
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int maxn = 1e6 + 5; const int maxm = 1e6; char str[maxn]; const pll mod = make_pair(1e9 + 7, 1e9 + 9); const pll base = make_pair(10007, 10009); pll fac[maxn]; map<pll, int> mp; 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) { 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; } bool check(char *str) { int len = strlen(str); pll hash = 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; init(); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", str); mp[getHash(str)] = 1; } while (m--) { scanf("%s", str); if (check(str)) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }