TKUDDUS - 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 and y are 0 based indexes).
Suppose 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 guaranteed that the summation of all the queries for each test case will not exceed 200000.
Example
Input: 1 abababc ab 3 0 6 1 2 0 4 Output: Case 1: 3 0 2
hide comments
merlin__:
2021-06-07 21:54:37
NlogN soln TLE'd in java :(((
|
|
nadstratosfer:
2019-06-25 05:11:27
Unexpected AC with nlogn in PyPy. Solved without knowing the constraints as the way the statement HTML is formatted, my custom dark CSS made them disappear. Nice problem, seemed easy at first, then too hard, then it turns out a prototype submitted to estimate the constraints gets the green bar. Will be back with linear solution when I get past the ugly bits of it. |
|
arszen123:
2016-04-20 21:55:16
I got wrong answear but why?
|
|
aditya_rev:
2016-04-11 18:05:59
i think it's very difficult to pass it, if the time limit just 0.5 s. To compare 10^6 character at least need 1s if using looping. |
|
kingw3:
2016-04-02 12:00:49
My solution is O(T*(S+q*log(q))),what is the optimal solution or the judge solution cause I get TLE |
|
[Rampage] Blue.Mary:
2016-04-01 12:58:24
My AC Program assumes nothing about character sets used in the problem. |
|
ivanstosic:
2016-04-01 12:43:50
What characters are allowed in the strings? |
|
arjundabra:
2014-11-16 09:04:44
please add more test cases |
|
[Lakshman]:
2014-11-05 11:39:13
@Raihat Zaman Neloy Can you please increase the Time limit here I am using Python with efficient algorithm But getting TLE. Thanks Last edit: 2014-11-05 11:41:33 |
|
Raihat Zaman Neloy:
2014-10-22 13:57:19
@tiwari: judge solution is, nlogn, but it can be also solved in linear time, and both the solutions are tested that it will passed the time limit. |
Added by: | Raihat Zaman Neloy |
Date: | 2014-10-16 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |