A famous streamer once said: "From now on, CRAZY GIVE HEAD!!". The streamer was so furious that he said many dirty words. You wonder how many times did a specific word appears in those words.
You will have one long string S and one short string p.
Then you will have q times of queries.
Each query includes two numbers a, b which indicate the range in string S.
The sum of a range indicates the occurrences of string p from position a of string S to position b of string S.
Your task is finding the maximum sum from all the queries.
Note that the index is start from 1.
For example:
You have S="ababaaaaba" and p="ba". You got q = 5, the five queries are as follow:
8 9
2 5
6 7
6 6
2 4
Position 8 to position 9 the occurrence of p equals 0
Position 2 to position 5 the occurrence of p equals 2
Position 6 to position 7 the occurrence of p equals 0
Position 6 to position 6 the occurrence of p equals 0
Position 2 to position 4 the occurrence of p equals 1
Therefore, the answer is 2.
Hint: The biggest problem is that if you construct a prefix sum array based on the occurrences of p[0] and check if it makes the entire p , you will get error when the range cut the "part of p".
Therefore consider this: if we want to avoid the "part of p" problem we can consider that if a part of p will be cut in range (L, R) that means p[0] must in the place of (R-length(p)+2, R). Therefore we only need to consider range (L,R-length(p)+1)
To sum up, we can change the range (L, R) into (L, R-length(p)+1). Use the prefix sum array to calculate this problem will be like: prefix[ R-length(p)+1 ] - prefix[ L-1 ]. In this way, we can avoid the "part of p" problem and solve the question.
⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠈⠉⠁⠈⠉⠉⠙⠿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⠄⠄⠄⠄⠄⠹⣿⣿⣿
⠄⠄⠄⠄⠄⢐⣲⣿⣿⣯⠭⠉⠙⠲⣄⡀⠄⠈⢿⣿
⠐⠄⠄⠰⠒⠚⢩⣉⠼⡟⠙⠛⠿⡟⣤⡳⡀⠄⠄⢻
⠄⠄⢀⣀⣀⣢⣶⣿⣦⣭⣤⣭⣵⣶⣿⣿⣏⠄⠄⣿
⠄⣼⣿⣿⣿⡉⣿⣀⣽⣸⣿⣿⣿⣿⣿⣿⣿⡆⣀⣿
⢠⣿⣿⣿⠿⠟⠛⠻⢿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣼
⠄⣿⣿⣿⡆⠄⠄⠄⠄⠳⡈⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠄⢹⣿⣿⡇⠄⠄⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⢿⣿⣷⣨⣽⣭⢁⣡⣿⣿⠟⣩⣿⣿⣿⠿⠿⠟
⠄⠄⠈⡍⠻⣿⣿⣿⣿⠟⠋⢁⣼⠿⠋⠉⠄⠄⠄⠄
⠄⠄⠄⠈⠴⢬⣙⣛⡥⠴⠂⠄⠄⠄⠄⠄⠄⠄⠄⠄...
(the photo of the famous streamer)
Input end with EOF.
Each testcase contains several lines.
First line contains two string S(1<= strlen(S) <= 1000) and p(1<= strlen(q)<=1000)
Second line one integer q(1 <= q <= 200000)
The following are q lines. Each line contain two integer a,b(1<= a <= b <= strlen(S))
For each testcases print the maximum sum from all the queries.
Remember to print \n at the end of each output.