概念

对于一个字符串$s = c_{n-1}c_{n-2}…c_0$，我们可以将其看成一个 $p$ 进制数，其十进制表示形式$x = c_{n-1} * p^{n-1} + c_{n-2} * p^{n-2} … + c_0 * p^0$ ，用 $x$ 来映射字符串 $s$ ，通常 $p = 131$ 或者 $p = 13331$ 导致冲突的概率会最小，hash值 $x$ 通常定义成 unsigned long long，让其自然溢出，达到 $mod 2^{64}$的目的。

下面给出字符串哈希的一些基本操作：

• 计算字符串s的哈希值：

  unsigned long long Hash = 0, p = 131;
  for(int i = 0; i < n; i++) {
    Hash = Hash*p + s[i];
  }
  

• 字符串s去掉最左端的字符，已知s的哈希值为Hash：

  Hash = Hash - s[0] * pow(p,m-1);
  

例题

2014 SERC J The Big Painting

题目链接

题意

给你两个图形 $p$ 和 $m$ ，大小分别为 $h_p$ $w_p$ $h_m$ $w_m$让你在 $m$ 中找一共有几个 $p$ 图形。

分析

本题用到了二维hash，对于第一个小图案，先将每行看成一个字符串进行一次hash，然后将每行的hash值看成一个字符组成一列字符串再进行一次hash得到key值用来映射这个二维图形。同样地，在大图形中，用mp[i][j] 表示第 $i$ 行第 $j$ 个长度为 $w_p$ 的字符串的hash值，然后用ha[i][j] 表示第 $i$ 行第 $j$ 个大小为 $h_p * w_p$ 的图形的hash值。

代码

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
ull mp[2100][2100], key, pp[2100], p[2100], ha[2100][2100], p2[2100];
char s[2100][2100];
int main(int argc, char const *argv[]) {
    int n, m, n2, m2;
    char x;
    cin >> n >> m >> n2 >> m2;
    //预处理p1和p2的幂
    p[0] = 1;
    for (int i = 1; i <= 2010; i++) {
        p[i] = p[i - 1] * 131;
    }
    p2[0] = 1;
    for (int i = 1; i <= 2010; i++) {
        p2[i] = p2[i - 1] * 13331;
    }
    //求小图案的hash值
    for (int i = 1; i <= n; i++) {
        getchar();
        ull c = 0;
        for (int j = 1; j <= m; j++) {
            scanf("%c", &x);
            c = c * p[1] + x;
        }
        key = key * p2[1] + c;
    }
    for (int i = 1; i <= n2; i++) {
        getchar();
        for (int j = 1; j <= m2; j++) scanf("%c", &s[i][j]);
    }
    //求每行的hash值
    for (int i = 1; i <= n2; i++) {
        for (int j = 1; j <= m2; j++) {
            if (j <= m) {//前m个字符组成第一个字符串，放在mp[i][1]中国
                mp[i][1] = mp[i][1] * p[1] + s[i][j];
            } else {
                mp[i][j - m + 1] =
                    mp[i][j - m] * p[1] + s[i][j] - s[i][j - m] * p[m];
            }
        }
    }
    //求二维hash
    for (int i = 1; i <= m2; i++) {
        for (int j = 1; j <= n2; j++) {
            if (j <= n) {
                ha[1][i] = ha[1][i] * p2[1] + mp[j][i];
            } else {
                ha[j - n + 1][i] =
                    ha[j - n][i] * p2[1] + mp[j][i] - mp[j - n][i] * p2[n];
            }
        }
    }
    LL res = 0;
    for (int i = 1; i <= n2 - n + 1; i++) {
        for (int j = 1; j <= m2 - m + 1; j++) {
            if (ha[i][j] == key) res++;
        }
    }
    cout << res;
    return 0;
}