字符串哈希
我们先来简述一下字符串哈希。首先我们把字符串中的字符转换为数值,比如我们使用以下函数来搞定:
\[toNum(character) = character – numberOf(‘a’) + 1\]
然后,我们来定义一个值\(bitNum\)来作为进位值。所以,我们的前缀哈希函数有一个递推式如下:
\[Hash(i) = Hash(i-1)*bitNum + toNum(S[i])\]
我们可以来探寻这个前缀哈希函数的相减线性性。我们设\(|S|,|T|\)为这两个字符串的长度。我们得出:
\[Hash(|T|) = Hash(|S+T|) – Hash(|S|)*bitNum^{|T|}(1.1)\]
本题思路
这道题目我们可以直接计算哈希前缀,然后根据公式\((1.1)\)来推出字串的哈希值,最后匹配即可。代码如下:
// CH1401.cpp
#include <iostream>
#define ull unsigned long long
using namespace std;
const int maxn = 1000200;
string DNAseq;
ull hs[maxn], bitNum = 133, pows[maxn];
int main()
{
cin >> DNAseq;
pows[0] = 1;
for (int i = 1; i <= DNAseq.length(); i++)
hs[i] = hs[i - 1] * bitNum + (DNAseq[i - 1] - 'a' + 1), pows[i] = pows[i - 1] * bitNum;
int T;
scanf("%d", &T);
while (T--)
{
int l1, l2, r1, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
ull hash1 = hs[r1] - hs[l1 - 1] * pows[r1 - l1 + 1];
ull hash2 = hs[r2] - hs[l2 - 1] * pows[r2 - l2 + 1];
if (hash1 == hash2)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
// CH1401.cpp
#include <iostream>
#define ull unsigned long long
using namespace std;
const int maxn = 1000200;
string DNAseq;
ull hs[maxn], bitNum = 133, pows[maxn];
int main()
{
cin >> DNAseq;
pows[0] = 1;
for (int i = 1; i <= DNAseq.length(); i++)
hs[i] = hs[i - 1] * bitNum + (DNAseq[i - 1] - 'a' + 1), pows[i] = pows[i - 1] * bitNum;
int T;
scanf("%d", &T);
while (T--)
{
int l1, l2, r1, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
ull hash1 = hs[r1] - hs[l1 - 1] * pows[r1 - l1 + 1];
ull hash2 = hs[r2] - hs[l2 - 1] * pows[r2 - l2 + 1];
if (hash1 == hash2)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
// CH1401.cpp #include <iostream> #define ull unsigned long long using namespace std; const int maxn = 1000200; string DNAseq; ull hs[maxn], bitNum = 133, pows[maxn]; int main() { cin >> DNAseq; pows[0] = 1; for (int i = 1; i <= DNAseq.length(); i++) hs[i] = hs[i - 1] * bitNum + (DNAseq[i - 1] - 'a' + 1), pows[i] = pows[i - 1] * bitNum; int T; scanf("%d", &T); while (T--) { int l1, l2, r1, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); ull hash1 = hs[r1] - hs[l1 - 1] * pows[r1 - l1 + 1]; ull hash2 = hs[r2] - hs[l2 - 1] * pows[r2 - l2 + 1]; if (hash1 == hash2) printf("Yes\n"); else printf("No\n"); } return 0; }