矩形

矩形

描述

给定两个矩阵，判断第二个矩阵在第一个矩阵的哪些位置出现过。

输入

输入的第一行包含四个正整数 a,b,c,d，表示第一个矩阵大小为 a×b，第二个矩阵的大小为c×d。

接下来是一个 a×b 的矩阵。再接下来是一个 c×d 的矩阵。

保证矩阵中每个数字都为正整数且不超过 100。

输

若第二个矩阵在第一个矩阵的(i,j)位置出现（即出现位置的左上角），输出i 和 j。若有多个位置，按字典序从小到大的顺序依次输出。

字典序：对于两个位置(a,b),(c,d)，若 a<c 则(a,b)比(c,d)小，若 a>c 则(a,b)比(c,d)大，若

a=c 则再像前边一样比较b 和 d。

样例 1 输入

4422

1212

2323

2123

2231

12

23

样例 1 输

11

13

32

样例 1 解释

矩阵 2 在矩阵 1 的(1,1)、(1,3)、(3,2)这些位置出现了。

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 50%的数据，a,b,c,d ≤ 50；

对于 100%的数据，a,b,c,d ≤ 1000。时间：4 sec

空间：512 MB

提示

[对于长度为 LL 的数列 SS, SS 中最大的元素为 KK，我们设他的 hashhash 值

H(S)=S1C0+S1C1+...+SLCL−1H(S)=S1C0+S1C1+...+SLCL-1, 其中 CC 为任意大于

KK 的常数]

[对于不同的字符串A,BA,B，H(A)≠H(B)H(A)≠H(B)]

[我们先来看看一维的情况，给定两个字符串 A,BA,B，我们怎么判断 AA 在BB 中出现？ 显然我们可以用hashhash 来判断。但是 hashhash 值太大了怎么办？取模呀！找一个比较好的质数pp，对于字符串 A,BA,B，若 A=BA=B 则显然H(A)modp=H(B)modpH(A)modp=H(B)modp；若 A≠BA≠B， H(A)modpH(A)modp 有一定概率会和H(B)modpH(B)modp 相同。怎么办呢？我们再找第二个质数pp，再来验证 H(A)modqH(A)modq 和 H(B)modqH(B)modq！可以证明，这样基本上是不会再出错了的。]

[拓展到二维。]

[对于第一个矩阵：]

[我们可以对每一个元素求向左长度为 dd 的矩阵元素的 hashhash 值，得到一个矩阵。] [然后我们再用新矩阵，再做一次 hashhash，就是向上长度为 cc 的矩阵元素的hashhash 值，得到新矩阵 XX。]

[接着我们将第二个字符串的 hashhash 值求出来，就是先每一行求一个 hashhash 值， 再将这 cc 个 hashhash 值再 hashhash 一次变成一个数字，然后我们就去XX 矩阵中找这个数字，找到多少个就说明第二个矩阵在第一个矩阵中出现了多少次。]

[时间复杂度 O(n2)O(n2)]

代码

#include <bits/stdc++.h> using namespace std;

// ================= 代码实现开始 =================

typedef long long ll; typedef pair<int, int> pii; const int N = 1005;

const ll mo1 = 1e9 + 7; const ll mo2 = 1e9 + 9; const ll pw = 233;

ll h1[2][N][N], h2[2][N][N], bb[2][N][N];

// 为了减少复制开销，我们直接读入信息到全局变量中

// a, b：题目所述数组，a的大小为(n+1)*(m+1)，b的大小为(p+1)*(q+1)，下标均从1开始有意义

（下标0无意义，你可以直接无视）

// n, m, p, q：题中所述

int a[N][N], b[N][N], n, m, p, q;

// 求出a中有哪些位置出现了b

// 返回值：一个pair<int, int>的数组，包含所有出现的位置vector<pii> getAnswer() {

ll p1 = 1, p2 = 1;

for (int i = 1; i <= q; ++i) {

p1 = p1 * pw % mo1;

p2 = p2 * pw % mo2;

}

p1 = (mo1 - p1) % mo1;

p2 = (mo2 - p2) % mo2;

for (int i = 1; i <= n; ++i) {

ll t1 = 0, t2 = 0;

for (int j = 1; j <= m; ++j) {

if (j < q) {

t1 = (t1 * pw + a[i][j]) % mo1;

t2 = (t2 * pw + a[i][j]) % mo2;

}

else {

t1 = h1[0][i][j] = (t1 * pw + a[i][j] + p1 * a[i][j - q]) % mo1;

t2 = h2[0][i][j] = (t2 * pw + a[i][j] + p2 * a[i][j - q]) % mo2;

}

}

}

p1 = 1, p2 = 1;

for (int i = 1; i <= p; ++i) {

p1 = p1 * pw % mo1;

p2 = p2 * pw % mo2;

}

p1 = (mo1 - p1) % mo1;

p2 = (mo2 - p2) % mo2;

for (int j = 1; j <= m; ++j) {

ll t1 = 0, t2 = 0;

for (int i = 1; i <= n; ++i) {

if (i < p) {

t1 = (t1 * pw + h1[0][i][j]) % mo1;

t2 = (t2 * pw + h2[0][i][j]) % mo2;

}

else {

t1 = h1[1][i][j] = (t1 * pw + h1[0][i][j] + p1 * h1[0][i - p][j]) % mo1;

t2 = h2[1][i][j] = (t2 * pw + h2[0][i][j] + p2 * h2[0][i - p][j]) % mo2;

}

}

}

for (int i = 1; i <= p; ++i)

for (int j = 1; j <= q; ++j) {

bb[0][i][j] = (bb[0][i][j - 1] * pw + b[i][j]) % mo1;

bb[1][i][j] = (bb[1][i][j - 1] * pw + b[i][j]) % mo2;

}

p1 = p2 = 0;

for (int i = 1; i <= p; ++i) {

p1 = (p1 * pw + bb[0][i][q]) % mo1;

p2 = (p2 * pw + bb[1][i][q]) % mo2;

}

vector<pii> ans;

for (int i = p; i <= n; ++i)

for (int j = q; j <= m; ++j)

if (h1[1][i][j] == p1 && h2[1][i][j] == p2)

ans.push_back(pii(i - p + 1, j - q + 1));

return ans;

}

// ================= 代码实现结束 =================

// ================= 代码实现结束 =================

int main() {

scanf("%d%d%d%d", &n, &m, &p, &q);

for (int i = 1; i <= n; ++i)

for (int j = 1; j <= m; ++j)

scanf("%d", &a[i][j]);

for (int i = 1; i <= p; ++i)

for (int j = 1; j <= q; ++j)

scanf("%d", &b[i][j]);

vector<pair<int, int>> ans = getAnswer();

for (int i = 0; i < int(ans.size()); ++i)

printf("%d %d\n", ans[i].first, ans[i].second);

return 0;

}