【CodeForces - 514C】Watto and Mechanism（字符串哈希）

题干：

输入n个字符串，然后进行m次询问，每次询问输入一个字符串，问n个字符串中是否存在与当前输入的字符串长度相等，并且刚好有且仅有一个位置的字符不同。存在则输出YES，不存在输出NO。

Examples

Input

2 3 aaaaa acacaca aabaa ccacacc caaac

Output

YES NO NO

解题报告：

   刚开始读错题了，还以为需要对于每一个询问，看n个模板串的子串是否有满足要求的解。但是题目中还要求两个串的长度需要相同，这样就简单多了，直接对于每个模板串，存下Hash值，直接放入set，对于每个询问，暴力修改位置，然后在set中查询就行了，刚开始单模数WA17了，脸黑、、改双模数就过了。（其实双模数用pair是最好的，因为这样有坑出现：两个Hash分别冲突了不同的值，也就是还是又概率出现冲突的，但是直接set<pair<ull,ull> >就几乎完全不会有问题）（wjhnb）

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; typedef unsigned ll ull; const int MAX = 6e5 + 5; const ll mod = 2000004199,mod2 = 1111111111111; const ll seed = 131,seed2 = 13331; int n,m; char s[MAX]; ull P[MAX],P2[MAX]; set<ull> ss,ss2; int main() {P[0]=P2[0]=1;for(int i = 1; i<MAX; i++) P[i] = P[i-1] * seed % mod,P2[i] = P2[i-1] * seed2 % mod2;cin>>n>>m;for(int i = 1; i<=n; i++) {scanf("%s",s+1);ull Hash = 0,Hash2 = 0;int len = strlen(s+1);for(int j = 1; j<=len; j++) Hash = (Hash*seed + s[j]-'a'+1)%mod,Hash2 = (Hash2*seed2+s[j]-'a'+1)%mod2;ss.insert(Hash);ss2.insert(Hash2);}for(int i = 1; i<=m; i++) {scanf("%s",s+1);ull Hash=0,Hash2 = 0;int len = strlen(s+1),flag = 0;for(int j = 1; j<=len; j++) Hash = (Hash*seed + s[j]-'a'+1)%mod,Hash2 = (Hash2*seed2+s[j]-'a'+1)%mod2;for(char ch = 'a'; ch<='c'; ch++) {for(int j = 1; j<=len; j++) {if(s[j] == ch) continue;if(ss.count((Hash+10*mod + (ch - s[j]) * P[len-j])%mod) && ss2.count((Hash2+10*mod2+(ch-s[j])*P2[len-j])%mod2)) {flag = 1;break; }}}if(flag == 1) puts("YES");else puts("NO");}return 0 ; }

 

总结

以上是生活随笔为你收集整理的【CodeForces - 514C】Watto and Mechanism（字符串哈希）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。