CH 1809
题意：求字符串$A$每个后缀与$B$匹配次数。
字符串Hash做法：
将$A, B$都Hash，然后枚举$A$的后缀(起始位置)，然后现在关键看$A, B$能最多匹配多少位。那么根据字符串的一类单调性，我们运用二分，固定左端点，二分右端点，然后就能求出。
KMP做法：
还不会先空着 qwq
知识点：
1、写程序多留点心静态差错要慢要仔细！
自然溢出 Hash 90分
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, m, q, cnt[200000 + 5];
unsigned LL ha[200000 + 5], hb[200000 + 5], p[200000 + 5], BS = 200;
char a[200000 + 5], b[200000 + 5];
unsigned LL getHash(unsigned LL *arr, int l, int r) {return arr[r] - arr[l - 1] * p[r - l + 1];}
void clean() {
ms(cnt, 0);
}
int solve() {
clean();
scanf("%d%d%d%s%s", &n, &m, &q, a + 1, b + 1);
ha[0] = hb[0] = 0, p[0] = 1;
for (int i = 1; i <= n; ++i) ha[i] = ha[i - 1] * BS + a[i];
for (int i = 1; i <= m; ++i) hb[i] = hb[i - 1] * BS + b[i];
for (int i = 1; i <= max(n, m); ++i) p[i] = p[i - 1] * BS;
// cerr << getHash(ha, 1, 2) << endl; cerr << getHash(hb, 1, 2) << endl;
for (int i = 1; i <= n; ++i) {
int l = i, r = min(n, i + m - 1) + 1, ans = -1;
//if (i == 3) cerr << "!!!" << l << " " << r << endl;
while (l < r) {
int mid = (l + r) >> 1;
//if (i == 3) cerr << "l: " << l << " r: " << r << " mid: " << mid << endl;
if (getHash(ha, i, mid) == getHash(hb, 1, mid - i + 1)) ans = mid, l = mid + 1; else r = mid;
}
//if (i == 3) cerr << "!!!" << ans << endl;
if (ans != -1) ++cnt[ans - i + 1]; else ++cnt[0];
}
while (q--) {
int x; scanf("%d", &x);
printf("%d\n", cnt[x]);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
双 Hash 满分
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, m, q, cnt[200000 + 5];
LL ha1[200000 + 5], hb1[200000 + 5], ha2[200000 + 5], hb2[200000 + 5], p1[200000 + 5], p2[200000 + 5], BS = 200, MO1 = 19260817, MO2 = 19660813;
char a[200000 + 5], b[200000 + 5];
LL getHash(LL *arr, LL *p, LL mod, int l, int r) {return (arr[r] - arr[l - 1] * p[r - l + 1] % mod + mod) % mod;}
void clean() {
ms(cnt, 0);
}
int solve() {
clean();
scanf("%d%d%d%s%s", &n, &m, &q, a + 1, b + 1);
ha1[0] = hb1[0] = 0, p1[0] = 1;
ha2[0] = hb2[0] = 0, p2[0] = 1;
for (int i = 1; i <= n; ++i) ha1[i] = (ha1[i - 1] * BS + a[i]) % MO1, ha2[i] = (ha2[i - 1] * BS + a[i]) % MO2;
for (int i = 1; i <= m; ++i) hb1[i] = (hb1[i - 1] * BS + b[i]) % MO1, hb2[i] = (hb2[i - 1] * BS + b[i]) % MO2;
for (int i = 1; i <= max(n, m); ++i) p1[i] = (p1[i - 1] * BS) % MO1, p2[i] = (p2[i - 1] * BS) % MO2;
for (int i = 1; i <= n; ++i) {
int l = i, r = min(n, i + m - 1) + 1, ans = -1;
while (l < r) {
int mid = (l + r) >> 1;
if ((getHash(ha1, p1, MO1, i, mid) == getHash(hb1, p1, MO1, 1, mid - i + 1)) && (getHash(ha2, p2, MO2, i, mid) == getHash(hb2, p2, MO2, 1, mid - i + 1)))
ans = mid, l = mid + 1; else r = mid;
}
if (ans != -1) ++cnt[ans - i + 1]; else ++cnt[0];
}
while (q--) {
int x; scanf("%d", &x);
printf("%d\n", cnt[x]);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
描述
阿轩在纸上写了两个字符串，分别记为A和B。利用在数据结构与算法课上学到的知识，他很容易地求出了“字符串A从任意位置开始的后缀子串”与“字符串B”匹配的长度。
不过阿轩是一个勤学好问的同学，他向你提出了Q个问题：在每个问题中，他给定你一个整数x，请你告诉他有多少个位置，满足“字符串A从该位置开始的后缀子串”与B匹配的长度恰好为x。
例如：A=aabcde，B=ab，则A有aabcde、abcde、bcde、cde、de、e这6个后缀子串，它们与B=ab的匹配长度分别是1、2、0、0、0、0。因此A有4个位置与B的匹配长度恰好为0，有1个位置的匹配长度恰好为1，有1个位置的匹配长度恰好为2。
输入格式
第一行三个整数N,M,Q，表示A串长度、B串长度、问题个数。
第二行是字符串A，第三行是字符串B。
接下来Q行每行1个整数x，表示一个问题。
1<=N,M,Q,x<=200000.
输出格式
共Q行，依次表示每个问题的答案。
样例输入
6 2 5
aabcde
ab
0
1
2
3
4
样例输出
4
1
1
0
0
来源
北京大学2015年数据结构与算法A期末考试
