Codeforces 514C Watto And Mechanism 哈希

题意:给出n个string,m次询问,判断string s是否和n个string中的某一个正好有一个位置不同. n,m<=3e5,并且string 只由a,b,c三种字符组成 总的字符串长度不超过6e5 正好要有一个位置不同,因为不同字符在某个位置上只有两情况, 把string插入到set中 暴力枚举位置后查询 O(|s|^2logn) set比较字符串要|s|...TLE.. 计算string的hash值,插入到set 枚举不同位置时 可以O(1)算出新的hash值 O(|s|logN)

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=6e5+20; const ll mod=1e9+7; const ll X=257; int n,m; string s,t,tmp; ll f[N]; set<ll> dic; void init() { f[0]=1; for(int i=1;i<N;i++) f[i]=(f[i-1]*X)%mod; } ll Hash(string s) { ll res=0; for(int i=0;s[i];i++) res=(res*X+s[i])%mod; return res; } bool check(string s) { ll h=Hash(s); ll len=s.length(); for(int i=0;s[i];i++) { for(ll c='a';c<='c';c++) { if(c==s[i]) continue; ll now=((((c-s[i])*f[len-1-i])%mod+mod)+h)%mod; if(dic.find(now)!=dic.end()) return true; } } return false; } int main() { cin.tie(0); ios::sync_with_stdio(false); init(); while(cin>>n>>m) { dic.clear(); for(int i=0;i<n;i++) { cin>>s; dic.insert(Hash(s)); } for(int i=0;i<m;i++) { cin>>t; if(check(t)) puts("YES"); else puts("NO"); } } return 0; }

dic: abcccc  acbaba 匹配: abbaba Trie匹配时只能dfs暴力匹配