Oulipo（暴力-字元串哈希hash）

judge：POJ 3461

Description

The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter ‘e’. He was a member of the Oulipo group. A quote from the book:

http://poj.org/problem?id=3461

Input

http://poj.org/problem?id=3461

Output

http://poj.org/problem?id=3461

Sample Input

3

BAPC

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

Sample Output

1

3

題意

給你兩個字元串，問你第一個串在第二個串中出現幾次（不同出現的地方可以重疊）

分别求兩個串的哈希值，O(n)比對即可。

代碼

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#define _for(i, a) for(int i = 0; i < (a); i++)
#define _rep(i, a, b) for(int i = (a); i <= (b); i++)
typedef unsigned long long ull;
const int maxn = 10005;
const int maxm = 1000005;
const int inf = 0x3f3f3f3f;
ull mod = 133;
using namespace std;

char a[maxn], b[maxm];
ull p[maxm], hs[maxm];

ull gethash(int l, int r) {
	return hs[r] - hs[l - 1] * p[r - l + 1];
}

int main() {
	p[0] = 1;
	_rep(i, 1, maxm - 1) p[i] = p[i - 1] * mod;

	int T;
	cin >> T;
	while (T--) {
		scanf("%s%s", a + 1, b + 1);
		ull a1 = 0;
		int alen = strlen(a + 1),
			blen = strlen(b + 1);
		_rep(i, 1, alen) {
			a1 = a1 * mod + (ull)a[i];
		}
		hs[0] = 0;
		_rep(i, 1, blen) {
			hs[i] = hs[i - 1] * mod + (ull)b[i];
		}
		int ans = 0;
		_rep(i, 1, blen - alen + 1) {
			if (a1 == gethash(i, i + alen - 1)) {
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}