WEAKSMK - Shoumiks Weakness
Shoumik loves problem solving but he is weak in string related problems. So he is practicing string related problems. But he thought that creating a string related problem and solving that would be a great idea to be strong in strings. So he thought of a problem.
Given a string S of N lower case letters how many distinct substrings T are there with length L (L = |T|) and S contains exactly X occurrences of T.
In the string S=“abcbcb” the substring T=“bcb” has length L=3 and S has X=2 occurrences of T. (See hints for more clarification)
But as Shoumik is weak in string, he is stuck with this problem. You have to help him answering Q queries for a given string S.
Input
First line of input will contain the number of test cases T. Then T test cases follows.
Every test case contains two integers N and Q in the first line. Next line will contain a string S, consisting of N lowercase characters.
The next Q lines will contain Q queries with two integers L, length of T for this query and X, occurrences of T in S.
1 <= T <= 15
1 <= N <= 10000
1 <= Q <= 100000
1 <= L < 2^31
0 <= X < 2^31
Sum of N over all test cases <= 60000 (6*10^4)
Number of queries Q over all test cases <= 600000 (6*10^5)
Output
For every query print the number of distinct substrings T in the string S which are of length L and have exactly X occurrences in S.
Example
Input: 1 6 5 abcbcb 3 2 4 1 6 2 6 1 1 2 Output: 1 3 0 1 1
Hints
For the 2nd query we have 3 distinct substrings of length 4 “abcb”, “bcbc”, “cbcb” and all of them have 1 occurrence in S. So the answer is 3.
For the 5th query we have 3 distinct substrings of length 1 “a”, “b”, “c” but only “c” has 2 occurrences in S. So the answer is 1.
hide comments
lawranoble:
2017-03-18 18:44:05
Can someone please give some hint
|
|
sahedsohel :
2016-09-13 22:58:43
thanks @prabhakar_jha examples are correct now..!! Last edit: 2016-09-13 22:59:11 |
|
prabhakar_jha:
2016-09-13 20:53:51
@sahedsohel:
|
|
sahedsohel :
2016-09-13 07:50:25
@abhishekpal : we cannot have any substring of bigger size then the given string..!! given that the constraints are OK...!! I suggest u read the prob again..!! |
|
abhishekpal:
2016-09-09 20:49:24
@sahedsohel :with a string of length 1000000 how can we have have a substring of size 2^31 and the input you provided doesn't consists of the tasks |
Added by: | sahedsohel |
Date: | 2016-09-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | https://algo.codemarshal.org/contests/goc-0101 |