题目描述

画家 $\text{Samuel}$ 有一幅原画（尺寸为 $h_p\times w_p$）和一幅由许多旧画拼接而成的巨作（尺寸为 $h_m\times w_m$）。两幅画都只包含两种字符：x 和 o 。现在要在巨作中找出原画所有可能出现的位置（允许重叠），输出位置的总数。

输入格式
多组测试数据，每组第一行包含四个整数 $h_p,w_p,h_m,w_m$ 。接下来 $h_p$ 行是原画，再接下来 $h_m$ 行是巨作。

约束条件
$1\le h_p,w_p,h_m,w_m\le 2000$ ，$h_p\le h_m$ ，$w_p\le w_m$ 。

输出格式
每组数据输出一个整数，表示原画在巨作中可能出现的位置数。

样例解释
原画尺寸 $4\times 4$ ，巨作尺寸 $10\times 10$ ，共有 $4$ 个匹配位置，部分位置可以重叠。

---

题目分析

本题是一个典型的 二维模式匹配 问题。模式矩阵 $P$ 尺寸为 $h_p\times w_p$ ，文本矩阵 $T$ 尺寸为 $h_m\times w_m$ ，需要统计 $P$ 在 $T$ 中所有出现的次数。

最朴素的做法是枚举 $T$ 中所有可能的左上角位置 $ (i, j) $ ，然后逐一比较 $h_p\times w_p$ 的字符是否与 $P$ 完全相同。枚举左上角需要 $O(h_m\cdot w_m)$ 次，每次比较需要 $O(h_p\cdot w_p)$ 时间，总复杂度为 $O(h_m\cdot w_m\cdot h_p\cdot w_p)$ 。在最坏情况下，$2000^4$ 的运算量显然不可接受，必须寻求更高效的算法。

字符串匹配中的 $\text{Rabin-Karp}$ 算法利用哈希将 $O(L)$ 的比较降为 $O(1)$ ，并利用滚动哈希在 $O(n)$ 时间内完成一维匹配。本题可以将其推广到二维：先对每行做一维滚动哈希，再对列方向做第二次哈希，从而实现 $O(1)$ 获取任意子矩阵的哈希值。将模式矩阵的哈希值与文本中所有 $h_p\times w_p$ 子矩阵的哈希值逐一比较，计数相等的个数即可。

---

解题思路

1. 哈希函数的选择

为了降低冲突概率，我们采用双哈希思想，但本题使用 自然溢出 代替模运算（$\text{unsigned long long}$ 自动对 $2^{64}$ 取模），同时选用两个不同的基数。

• 行哈希基数：$\text{BASE1}$ ，用于计算每一行字符串的哈希值。
• 列哈希基数：$\text{BASE2}$ ，用于组合不同行的哈希值。

定义字符映射：'x' 映射为 $1$ ，'o' 映射为 $0$ （也可以反过来，只要保证不同字符映射值不同即可）。

2. 一维滚动哈希

对于字符串 $s[\mathrm{0..}n-1]$ ，其哈希值定义为：
$$hash(s)=s[0]\cdot {\text{BASE}}^{n-1}+s[1]\cdot {\text{BASE}}^{n-2}+\cdots +s[n-1]\cdot {\text{BASE}}^0$$
但为了方便滚动更新，通常采用 左乘累加 的形式：
$$h[0]=s[0]$$
$$h[i]=h[i-1]\cdot \text{BASE}+s[i]$$
这样，子串 $s[l..r]$ 的哈希值可以通过前缀哈希求出：
$$hash(l,r)=h[r]-h[l-1]\cdot {\text{BASE}}^{r-l+1}$$
代码中我们使用 rowHash[i][j] 表示第 $i$ 行（从 $1$ 开始计数）前 $j$ 个字符的哈希值。

3. 二维哈希构造

有了每行的前缀哈希后，我们可以对整个矩阵构造二维哈希。定义二维哈希数组 $H[i][j]$ 表示左上角为 $(1,1)$ ，右下角为 $(i,j)$ 的子矩阵的哈希值。

构造方式：先按行方向计算每行的哈希，然后按列方向组合：

• 对于每一行 $i$ ，我们已经得到了 rowHash[i][j]（表示该行前 $j$ 列的哈希）。
• 然后在列方向使用基数 $\text{BASE2}$ 滚动：
  $$H[i][j]=H[i-1][j]\cdot \text{BASE2}+rowHash[i][j]$$

这样，$H[i][j]$ 就唯一表示了从 $(1,1)$ 到 $(i,j)$ 的矩形区域的哈希值，其中行方向贡献指数 ${\text{BASE2}}^{i-1}$ ，列方向贡献指数 ${\text{BASE1}}^{j-1}$ 。

4. 子矩阵哈希提取

要得到左上角 $(r_1,c_1)$ ，右下角 $(r_2,c_2)$ 的子矩阵哈希值，公式为：
$$\begin{array}{rl}subHash=& H[r_2][c_2]\\ & -H[r_1-1][c_2]\cdot \text{pow2}[r_2-r_1+1]\\ & -H[r_2][c_1-1]\cdot \text{pow1}[c_2-c_1+1]\\ & +H[r_1-1][c_1-1]\cdot \text{pow1}[c_2-c_1+1]\cdot \text{pow2}[r_2-r_1+1]\end{array}$$

其中 $\text{pow1}[k]={\text{BASE1}}^k$ ，$\text{pow2}[k]={\text{BASE2}}^k$ 。这个公式可以理解为二维前缀和的哈希版本，减去左上方多余的部分，再加上被减两次的左上角重叠部分。

对于本题，子矩阵尺寸固定为 $h_p\times w_p$ ，因此 $r_2=r_1+h_p-1$ ，$c_2=c_1+w_p-1$ 。子矩阵的哈希值可以在 $O(1)$ 时间内计算。

5. 模式哈希计算

模式矩阵 $P$ 的哈希值采用与文本完全相同的构造方式：先逐行计算行哈希，再按列组合。这样，模式哈希与文本子矩阵哈希可以直接比较。

6. 复杂度分析

• 计算所有行的前缀哈希：$O(h_m\cdot w_m)$ 。
• 计算二维哈希数组：$O(h_m\cdot w_m)$ 。
• 枚举所有可能的左上角位置：$O(h_m\cdot w_m)$ ，每个位置 $O(1)$ 时间比较。
• 总时间复杂度 $O(h_m\cdot w_m)$ ，空间复杂度 $O(h_m\cdot w_m)$ 。

对于 $2000\times 2000$ 的数据规模，完全可行。

7. 注意事项

• 使用 unsigned long long 自然溢出，无需手动取模，效率高且冲突概率极低。
• 预计算 $\text{pow1}$ 和 $\text{pow2}$ 数组到最大维度，避免重复计算幂。
• 字符映射为 $0$ 和 $1$ 可以避免 'o' 和 'x' 的 $\text{ASCII}$ 码差异过大导致哈希值分布不佳，但不是必须。
• 读入时注意 cin 与 $ios::sync_with_stdio(false) 配合以加速输入。

---

代码实现

// The Big Painting
// UVa ID: 12886
// Verdict: Accepted
// Submission Date: 2026-05-23
// UVa Run Time: 0.110s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

typedef unsigned long long ULL;

const ULL BASE1 = 911382323;   // 行哈希基数
const ULL BASE2 = 972663749;   // 列哈希基数

int hp, wp, hm, wm;
vector<string> pattern, text;

void solve() {
    // 读入原画
    pattern.resize(hp);
    for (int i = 0; i < hp; ++i) cin >> pattern[i];
    // 读入巨作
    text.resize(hm);
    for (int i = 0; i < hm; ++i) cin >> text[i];

    // 预计算幂
    vector<ULL> pow1(max(wm, wp) + 1), pow2(max(hm, hp) + 1);
    pow1[0] = pow2[0] = 1;
    for (int i = 1; i <= max(wm, wp); ++i) pow1[i] = pow1[i - 1] * BASE1;
    for (int i = 1; i <= max(hm, hp); ++i) pow2[i] = pow2[i - 1] * BASE2;

    // 计算模式矩阵的哈希值
    ULL patternHash = 0;
    for (int i = 0; i < hp; ++i) {
        ULL rowHash = 0;
        for (int j = 0; j < wp; ++j) {
            ULL val = (pattern[i][j] == 'x') ? 1 : 0;
            rowHash = rowHash * BASE1 + val;
        }
        patternHash = patternHash * BASE2 + rowHash;
    }

    // 计算文本矩阵每行的前缀哈希
    vector<vector<ULL>> rowHash(hm + 1, vector<ULL>(wm + 1, 0));
    for (int i = 1; i <= hm; ++i)
        for (int j = 1; j <= wm; ++j) {
            ULL val = (text[i - 1][j - 1] == 'x') ? 1 : 0;
            rowHash[i][j] = rowHash[i][j - 1] * BASE1 + val;
        }

    // 计算文本矩阵的二维哈希
    vector<vector<ULL>> hash2D(hm + 1, vector<ULL>(wm + 1, 0));
    for (int i = 1; i <= hm; ++i)
        for (int j = 1; j <= wm; ++j)
            hash2D[i][j] = hash2D[i - 1][j] * BASE2 + rowHash[i][j];

    // 枚举所有可能的左上角位置
    int ans = 0;
    for (int i = hp; i <= hm; ++i)
        for (int j = wp; j <= wm; ++j) {
            int r1 = i - hp + 1, c1 = j - wp + 1;
            ULL subHash = hash2D[i][j]
                        - hash2D[r1 - 1][j] * pow2[hp]
                        - hash2D[i][c1 - 1] * pow1[wp]
                        + hash2D[r1 - 1][c1 - 1] * pow1[wp] * pow2[hp];
            if (subHash == patternHash) ++ans;
        }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> hp >> wp >> hm >> wm) solve();
    return 0;
}

---

总结

本题利用 二维滚动哈希 将二维模式匹配的时间复杂度从 $O(h_m{w}_m{h}_p{w}_p)$ 降至 $O(h_m{w}_m)$ ，在 $2000$ 量级的数据下能够高效运行。核心思想是将矩阵按行和列两个方向分别进行哈希累加，从而支持 $O(1)$ 提取任意子矩阵的哈希值。该方法也适用于更一般的二维模式匹配问题，例如图像匹配、文本检索等场景。