当前位置：网站首页>String hashing (2014 SERC J question)

String hashing (2014 SERC J question)

2022-08-09 23:14:00 【Here_SDUT】

Concept

For a string s = c_{n-1}c_{n-2}…c_0, we can treat it as a p base number,Its decimal representation x = c_{n-1} * p^{n-1} + c_{n-2} * p^{n-2} … + c_0 * p^0 ,Use x to map the string s, usually p = 131 or p = 13331 will cause the least chance of conflict, the hash value x is usually defined as unsigned long long, allowing it to overflow naturally to achieve the purpose of mod 2^{64}.

Some basic operations on string hashing are given below:

Calculate the hash value of string s:

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

The leftmost character is removed from the string s, and the hash value of s is known as Hash:

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

Example

2014 SERC J The Big Painting

topic link

Title

Give you two graphics p and m, the size is h_pw_ph_mw_m allows you to find a total of several p graphics in m.

Analysis

This question uses two-dimensional hash. For the first small pattern, first hash each line as a string, and then use the hash value of each line as a character to form a column of strings and then hash it again to getThe key value is used to map this two-dimensional graph.Similarly, in a large graph, use mp[i][j] to represent the string of length w_p at line i and jThe hash value of , and then use ha[i][j] to represent the hash of the graph whose size is h_p * w_p at the i line jvalue.

Code

#include #define LL long long#define ull unsigned long longusing namespace std;const int maxn = 1e5 + 10;const int inf = 0x3f3f3f3f;const double PI = acos(-1.0);typedef pair 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;//Preprocess the powers of p1 and p2p[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;}/ / Find the hash value of the small patternfor (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]);}// find the hash value of each rowfor (int i = 1; i <= n2; i++) {for (int j = 1; j <= m2; j++) {if (j <= m) {//The first m characters form the first string, which is placed in mp[i][1]Chinamp[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];}}}//Seek two-dimensional hashfor (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://yzsam.com/2022/221/202208092049543826.html