题目描述
思路
这题本质叫我们求两个序列中差值相等的串的数量,我们可以做一下差然后跑kmp即可
#include#define N 1000001 int p[N], a[N], b[N], c[N], d[N]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &c[i]); for (int i = 1; i <= m; i++) scanf("%d", &d[i]); for (int i = 0; i <= n; i++) a[i] = c[i + 1] - c[i + 2]; for (int i = 0; i <= n; i++) b[i] = d[i + 1] - d[i + 2]; n--; m--; p[0] = -1; int j = -1; for (int i = 1; i < m; i++) { while (b[i] != b[j + 1] && j != -1) j = p[j]; if (b[i] == b[j + 1]) j++; p[i] = j; } j = -1; int ans = 0; for (int i = 0; i < n; i++) { while (a[i] != b[j + 1] && j != -1) j = p[j]; if (a[i] == b[j + 1]) j++; if (j == m - 1) { ans++; j = p[j]; } } printf("%d\n", ans); }
]]>
Comments NOTHING