算法二十四：矩形

分手后的思念是犯贱 2022-05-21 08:10 143阅读 0赞

### **描述** ###

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

### **输入** ###

输入的第一行包含四个正整数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输入** ###

4 4 2 2
    1 2 1 2
    2 3 2 3
    2 1 2 3
    2 2 3 1
    1 2
    2 3

### **样例1输出** ###

1 1
    1 3
    3 2

### **样例1解释** ###

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

### **一. 伪代码** ###

![70][]

### **![70 1][]**![70 2][] ###

### **二. 具体实现（C++）** ###

\#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;  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220521/e746438441b6436ba5c90ab5faadfc87.png
[70 1]: https://img-blog.csdn.net/20180703152631686?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220521/b53441a61ba1462b83d0385a5027888a.png