spoj#TKUDDUS. Taklu Kuddus
Taklu Kuddus
Kuddus is a great programmer. He recently solved 100 problems in different OJ’s. One day his girlfriend gave him a problem. But he failed to solve that problem and his girlfriend became very angry.
For this reason his girlfriend don’t talk to him.
He is losing his hair by thinking of how he can solve the problem. Now kuddus came to you for help. As his friend, you have to help kuddus and save his relation and hair also.
The problem is, you are given a string “S” and a pattern “P”. You have to find FS (x, y) that is defined as the maximum number of non-overlapping substring which is equal to the pattern “P” in the substring
of S which starts at x and end at y (x ,y are in 0 base indexes ) .
S = “abcdef”
P = “cd”
and the query is (1,5) , so the substring will be “bcdef” and FS(1,5) = 1
Input
First line contains an integer T (number of test cases)(1<=T<=10)
Each case starts with a line containing string S, |S| <= 1000000. The next line contains string P, |P| <= 1000000.
Then an integer q(1<=q<=100000) , Each of the next q lines will contain a query which is in the form i j
( 0≤ i ≤ j <length(S) ).
Output
For each test case, print the case number in a single line.
Then for each query you have to print a line , value of FS(i.j) ;
It is guaranted that the summation of all the queries for each test case will not exceed 200000
Example
Input:1
Output:
abababc
ab
3
0 6
1 2
0 4Case 1:
3
0
2