- UVA 11019 - Matrix Matcher
- #include <bits/stdc++.h>
- using namespace std;
- #define rint register int
- #define rll register long long
- typedef long long ll;
- const int maxn = 1e3 + 100;
- const int base1 = 233, base2 = 2333;
- char a[maxn][maxn], b[maxn][maxn];
- unsigned long long ha[maxn][maxn], hb[maxn][maxn];
- int main() {
- freopen("in.txt", "r", stdin);
- rint _;
- scanf("%d", &_);
- while (_--) {
- rint n, m, x, y;
- scanf("%d %d", &n, &m);
- for (rint i = 1; i <= n; i++)
- scanf("%s", a[i] + 1);
- scanf("%d %d", &x, &y);
- for (rint i = 1; i <= x; i++)
- scanf("%s", b[i] + 1);
- register unsigned long long p1 = 1, p2 = 1;
- for (rint i = 1; i <= x; i++) {
- p2 *= base2;
- }
- for (rint i = 1; i <= y; i++) {
- p1 *= base1;
- }
- for (rint i = 1; i <= x; i++) {
- for (rint j = 1; j <= y; j++) {
- hb[i][j] = (b[i][j] - 'a') + hb[i][j - 1] * base1 + hb[i - 1][j] * base2 -
- hb[i - 1][j - 1] * base1 * base2;
- }
- }
- rint ans = 0;
- for (rint i = 1; i <= n; i++) {
- for (rint j = 1; j <= m; j++) {
- ha[i][j] = (a[i][j] - 'a') + ha[i][j - 1] * base1 + ha[i - 1][j] * base2 -
- ha[i - 1][j - 1] * base1 * base2;
- if (i>= x && j>= y &&
- hb[x][y] == ha[i][j] - ha[i - x][j] * p2 - ha[i][j - y] * p1 + ha[i - x][j - y] * p1 * p2) {
- ans++;
- }
- }
- }
- printf("%d\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3147887.html