Oulipo （哈希）

求模式串在待匹配串的出现次数。

Input

第一行是一个数字T，表明测试数据组数。
之后每组数据都有两行：第一行为模式串，长度不大于10000；第二行为待匹配串，长度不大于1000000。所有字符串只由大写字母组成。

Output

每组数据输出一行结果。

Sample Input

4
ABCD
ABCD
ABA
ABABABA
CDCDCDC
CDC
KMP
NAIVE

Sample Output

1
3
0
0

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxm = 1e4 + 5;
const int maxn = 1e6 + 5;
char w[maxm],t[maxn];
ull p = 233;
int main()
{
	int tt;
	scanf("%d",&tt);
	while (tt--)
	{
		int i,j;
		scanf("%s %s",w,t);
		int len1 = strlen(w);
		int len2 = strlen(t);
		if (len1>len2)
		{
			printf("0\n");
			continue;
		}
		ull k = 1;
		for (i=0;i<len1;i++)
			k *= p;
		ull wh = 0,th = 0;
		for (i=0;i<len1;i++)
		{
			wh = wh * p + w[i] - 'A' + 1;
			th = th * p + t[i] - 'A' + 1;
		}
		int cnt = 0;
		for (i=0;i+len1<=len2;i++)
		{
			if (wh==th)
				cnt++;
			if (i+len1<len2)
				th = th * p + (t[i+len1] - 'A' + 1) - (t[i] - 'A' + 1) * k;
		//例如：w:12303		t:212303 
		//		wh 12303  	p假设就是10，因为hash也是转化为p进制的，p就是10进制中的数量级 
		//		th 21230 	上式中的k为100000,k就是数量级 
		//      假设th 的下一位是3 
		//		th =  21230 * 10 + 3 - 2 * 100000
		//		   = 12303 
		//这一步的意思就是这样，简单说就是去掉第一个字符后面再加上 一个字符，就这样循环下去 
		}
		printf("%d\n",cnt);
 	}
 	return 0;
}