zoj3618 Hash Function

Hash Function Time Limit: 3 Seconds       Memory Limit: 65536 KB

Hash table is very important in computer science. A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person's name, having a variable length, could be hashed to a single integer. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

Polynomial hash function is a simple kind of hash function as follow: Assume the key is of the form of a Object with multiple components, (x0, x1, x2, ..., xk-1), for example a string, the individual objects characters. Given a positive integer b, we use the polynomial function f defined below as a naive hash function: f(x,b) = x0bk-1 + x1bk-2 + ... + xk-2b + xk-1 . Because the value of f(x,b) is too large, we usually take the remainder of it divided by a particular prime integer P larger than b.

Here comes the problem, given a string S, a hash function f and integer N, calculate how many substrings(non-empty consecutive characters) of S whose hash value is N.

Input

There are multiple test cases. The first line of input is an integer T(T ≈ 100) indicates the number of test cases. Then T test cases follow. Each test case contains 2 lines. The first line of each test case is a line containing a string S. The second line is an integer b , a prime integer P and another integer N separated by a space. The length of the string S is no longer than 10000 and all the characters are printable whose ASCII value is between 32 and 126 inclusive, 0 <=b,N <P <231.

Output

Output the answer in a single line.

Sample Input

2
BBB
1 2 1
BBB
1 2 0      

Sample Output

0
6      

Hint

In both of the 2 samples, the hash value of all the substrings are even because the ASCII value of B is 66. There is 1 substring BBB whose hash value is 198. There are 2 substrings BB whose hash value are 132. There are 3 substrings B whose hash value are 66.

Author:  CAO, Peng

Contest: ZOJ Monthly, June 2012

題意:

第一行是case數

接下來case個資料塊

每個是這樣的，第一行是一串字元串，

第一行是三個數字b,p,n

由題目公式看f(x,b) = x0bk-1 + x1bk-2 + ... + xk-2b + xk-1

最後f(x,b)%p

本題求得是該字元串的子串用這個公式算出的值等于n的有多少個！

如BBB,b為1,p為2,n為0

有3個含有1個B的子串

f(x,b)=66(B的ACSII碼)*1^0=66

有兩個含有2個B的子串

f(x,b)=66*1^1+66*1^0=132

有1個含有3個B的子串

f(x,b)=66*1^2+66*1^1+66*1^0=198

而這三個f(x,b)%p(p為2)均為0(N的值）

是以全滿足！、

那麼一共是3+2+1=6個

即case2輸出6

分析:

這是一道字元串哈希的題目，因為字元串有1W長度，是以直接暴力顯然不可行，那麼我們隻能用字首的思想儲存一部分的字元串的值。

首先想一個字元串如果要取餘之後等于n那麼它肯定是由别的子串構成的

我們構造一個字首和是從後往前前n個串的f(x,b)

以上述BBB的例子

sum[1]=66*1^2+66*1^1+66*1^0

sum[2]=66*1^1+66*1^0

sum[3]=66*1^0

那麼設t=sum[3]+n,如果t這個串有幾個就是有幾個滿足的

同理t=sum[2]+n,t=sum[1]+n

而這個n是要轉換的

如這個圖，n是要轉化的，但是如何轉化最效率呢

聰明的讀者一定早就知道了！

n=n*b^i%p次

那麼用map儲存字首，然後即可！

code:

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
map <long long,int> mm;
char str[10010];
long long sum[10010],p,B[10010],a[10010],js[10010];
int main()
{
	int T,b,n,len,i,k;
	long long ans,t;
	scanf("%d",&T);
	getchar();
	while(T--){
		mm.clear();
		gets(str);
		scanf("%d%d%d",&b,&p,&n);
		getchar();
		ans=0;
		len=strlen(str);
		for(i=0;i<len;i++)
			a[i]=str[i]-0;
		sum[len]=0;
		B[len]=1;
		for(i=len-1;i>=0;i--){
			sum[i]=(sum[i+1]+a[i]*B[i+1]%p)%p;
			B[i]=B[i+1]*b%p;
			if(mm.find(sum[i])==mm.end())
				mm[sum[i]]=1;
			else
				mm[sum[i]]++;
		}
		if(mm.find(n)!=mm.end())
			ans+=mm[n];
		for(i=len-1;i>0;i--){
			t=(B[i]*n%p+sum[i])%p;
			mm[sum[i]]--;//為何這裡要減減呢！，考慮下BBB的情況你就知道了
			if(mm.find(t)!=mm.end()){
				ans+=mm[t];
			}
		}
		printf("%lld\n",ans);
	}
}