POJ3461 字符串哈希_poj3461()hash

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
 
#define ll long long 
#define ull unsigned long long 
#define mxn 1002000
#define eps 1e-8
 
char t[mxn], w[mxn];
ull h[mxn], p[mxn];
ull geth( int l, int r ) {
	return h[r] - h[ l - 1 ] * p[ r - l + 1];
}
int main() {
	int cas;
	p[0] = 1;
	for( int i = 1; i < mxn; ++i ) 
		p[i] = p[i-1] * 133;
	scanf( "%d", &cas );
	while( cas-- ) {
		scanf( "%s", w + 1 );
		scanf( "%s", t + 1 );
		ull cnt = 0;
		int wn = strlen( w + 1 );
		for( int i = 1; i <= wn; ++i ) 
			cnt = cnt * 133 + w[i];
		h[0] = 0;
		int n = strlen( t + 1 );
		for( int i = 1; i <= n; ++i ) 
			h[i] = h[i-1] * 133 + t[i];
		int ans = 0;
		for( int i = 1; i <= n - wn + 1; ++i )
			if( cnt == geth( i, i + wn - 1 ) )
				ans++;
		printf( "%d\n", ans );
	}
	return 0;
}