二维哈希

题意：给定一个由和0组成的大小为nm的匹配对象，和T个大小为pq的匹配模式，求匹配对象中至少出现一次匹配模式的个数
思路：将每一行看成一个字符串，计算从每个位置开始长度为Q的字符串子串的哈希值，然后把得到的哈希值在列方向看成一个字符串，计算每个位置开始长度为P的字符串子串的哈希值，通过上述步骤，可以得到这个nm的匹配对象的所有的pq的子阵的哈希值*

注意：两次哈希值的计算选用不同的基数

样例：

输入：
3 3 2 2 2
*00
0**
*00

**
00

*0
**
3 3 2 2 2
*00
0**
*00

**
00

*0
0*
0 0 0 0 0

输出：
Case 1: 1
Case 2: 2

菜鸡根据理解写的哈希代码，等有能力了再用AC自动机自闭一会，(#^.^#)

#include<stdio.h>
#include<string.h>
#include<set>
using namespace std;
const int maxn = 1001;
typedef unsigned long long ull;
int N, M, T, P, Q;
char field[maxn][maxn];//匹配对象
char patterns[101][maxn][maxn];
ull Hash[maxn][maxn], tmp[maxn][maxn];
//计算a的所有的p*q子阵对应的哈希值
void compute_Hash(char a[maxn][maxn], int n, int m) {
	const ull B1 = 9937;//按行计算时的基数
	const ull B2 = 1e8 + 7;
	ull t1 = 1; //B1的Q次方
	for (int j = 0; j < Q; j++)
		t1 *= B1;
	//按行方向计算哈希值
	for (int i = 0; i < n; i++) {
		ull e = 0;
		//计算此行长度为Q的前缀对应的哈希值
		for (int j = 0; j < Q; j++)
			e = e * B1 + a[i][j];      
		//不断对这一整行向右移一位，更新哈希值并判断
		for (int j = 0; j + Q <= m; j++) {
			tmp[i][j] = e;
			if (j + Q < m)
				e = e * B1 - t1 * a[i][j] + a[i][j + Q];
		}
	}
	ull t2 = 1;
	for (int i = 0; i < P; i++)
		t2 *= B2;
	//按列方向计算哈希值
	//有行子串的前提下
	for (int j = 0; j + Q <= m; j++) {
		ull e = 0;
		//按列计算哈希值，此时列上的值是行哈希后的值
		for (int i = 0; i < P; i++)
			e = e * B2 + tmp[i][j];
		for (int i = 0; i + P <= n; i++) {
			Hash[i][j] = e;
			if (i + P < n)
				e = e * B2 + tmp[i + P][j] - t2 * tmp[i][j];
		}
	}
}
int solve() {
	//将所有模式的哈希值放入multiset
	//multiset允许有重复的数字
	//logn的复杂度，内部以平衡二叉树实现
	multiset<ull>unseen;
	for (int k = 0; k < T; k++) {
		//计算模式矩阵的哈希值
		compute_Hash(patterns[k], P, Q);
		unseen.insert(Hash[0][0]);
	}
	//将出现的哈希值从multist中删除
	//计算匹配对象的所有子模式矩阵的哈希值
	compute_Hash(field, N, M);
	for (int i = 0; i + P <= N; i++) {
		for (int j = 0; j + Q <= M; j++)
			unseen.erase(Hash[i][j]);
	}
	//剩下的哈希值的个数就是没有出现的模式矩阵的个数
	int ans = T - unseen.size();
	return ans;
}
int main()
{
	int flag = 1;
	while (~scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q)) {
		if (!N && !M && !T && !P && !Q)
			break;
		//memset(field, '\0', sizeof(field));
		//memset(patterns, '\0', sizeof(patterns));
		for (int i = 0; i < N; i++)
			scanf("%s", field[i]);
		for (int i = 0; i < T; i++) {
			for (int j = 0; j < P; j++)
				scanf("%s", patterns[i][j]);
		}
		int ans = solve();
		printf("Case %d: %d\n", flag++, ans);
	}
	return 0;
}