当前位置：网站首页>字符串哈希（2014 SERC J题）

字符串哈希（2014 SERC J题）

2022-08-09 20:51:00 【Here_SDUT】

概念

对于一个字符串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_pw_ph_mw_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;
}

原网站

版权声明
本文为[Here_SDUT]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2069182