
117  ZOJ Monthly, June 2012  H
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, (x_{0}, x_{1}, x_{2}, ..., x_{k1}), 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) = x_{0}b^{k1} + x_{1}b^{k2} + ... + x_{k2}b + x_{k1} . 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(nonempty consecutive characters) of S whose hash value is N. InputThere 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 <2^{31}. OutputOutput the answer in a single line. Sample Input2 BBB 1 2 1 BBB 1 2 0 Sample Output0 6 HintIn 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 