String Matching

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
In this problem we will have a few definitions as described below:
 Binary string: A string containing only characters '0' and '1'.
 Hamming distance of the two binary string of the same length is the number of the positions where the two strings have
different characters. eg. the hamming distance of "01010101" and
"00110111" is 3, the hamming distance of a binary string with itself is 0.  Substring of a string is a segment of contiguous characters of that string.
You would be given two binary strings A and B with the length of N and M respectively.
You need to calculate the Hamming distance between B and every substrings of length M of A.
For this problem, you will be given a fixed string A. There will be K queries each containing a string representing B.
Input
 The first line contains the binary string A.
 The next line contains an integer K.
 Each of the next K lines contains a binary string B.
Output
To avoid generating large output, for each query string B instead of printing N  M + 1 values of Hamming distance between
substrings of A and B in the order of the position of the substring in A, you only need to print
the hash value of this sequence as described below.
Let s[0..L 1] be a sequence of L integers. The recursive function f(s) will return the hash value of s.
 if L = 1, f(s) = s[0] mod 1000000007
 Otherwise, f(s) = (f(s[0..L2]) * 100001 + s[L1]) mod 1000000007
So overall, your output should be K lines, each containing the hash value corresponding to the query string B.
Constraints
20 points:
 1 ≤ M ≤ N ≤ 1000
 1 ≤ K ≤ 5
40 points:
 1 ≤ M ≤ N ≤ 50000
 1 ≤ K ≤ 5
40 points:
 1 ≤ M ≤ N ≤ 100000
 1 ≤ K ≤ 5
Example
Input: 10101 3 101 00 0101 Output: 300003 993599731 400004
Explanation:
First test case: A = "10101", B = "101".
The Hamming distances sequence will be (0, 3, 0) and the hash value of this sequence is 300003.
Second test case: A = "10101", B = "00". The Hamming distances sequence will be (1, 1, 1, 1)
and the hash of this sequence is 993599731.
Third test case: A = "10101", B = "0101". The Hamming distances sequence will be (4, 0)
and the hash value of this sequence is ((4 mod 1000000007) * 100001 + 0) mod 1000000007 = 400004.
Author:  tuananh93 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/TASTRMAT 
Tags  fft, hard, ltime19, tuananh93 
Date Added:  6122014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 