Sample test(s)
input
2 3aaaaaacacacaaabaaccacacccaaac
output
YESNONO题目要求，给一个字符串集，给定一个字符串，字符串集是否存在这个字符串相差一个字符的字符串，字符串很多，而且很长，想要存下来是不可能的，就算能存下来，一个个比较查询也是不可能的，所以要用hash，这样查询很快，用set存复杂度为，n*logm了，设计hash函数，因为只有 a b c三种字符，所以，可以用4进制数存，每一位为1 2 3，，这样计算hash值后，查询就可以了！#define N 600005#define MOD 1000000000000000007int n,m;ll pri[N];set<ll> mysets;char str[N];ll getHash(){ll ans = 0;for(int i=0;str[i];i++){ans += (str[i] – 'a' + 1) * pri[i] % MOD;ans %= MOD;}return ans;}bool check(){ll ans = getHash(),temp;for(int i=0;str[i];i++){for(int j=1;j<=3;j++)if(j !=(str[i] – 'a' + 1)) {temp = (ans – (str[i] – 'a' + 1) * pri[i] % MOD + j * pri[i] % MOD + MOD)%MOD;if(mysets.count(temp))return true;}}return false;}int main(){pri[0] = 1;for(int i=1;i<N;i++){pri[i] = pri[i-1] * 4 % MOD;}while (S2(n,m) != EOF){mysets.clear();FI(n){SS(str);mysets.insert(getHash());}FI(m){SS(str);if(check())printf("YES\n");elseprintf("NO\n");}}return 0;}
明天的希望，让我们忘了今天的痛苦
