问题 B: Classic Quotation 问题 B: Classic Quotation
时间限制: 8 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:]题目描述
When online chatting, we can save what somebody said to form his ''Classic Quotation''. Little Q does this, too. What's more? He even changes the original words. Formally, we can assume what somebody said as a string S
whose length is n
. He will choose a continuous substring of S
(or choose nothing), and remove it, then merge the remain parts into a complete one without changing order, marked as S′
. For example, he might remove ''not'' from the string ''I am not SB.'', so that the new string S′
will be ''I am SB.'', which makes it funnier.
After doing lots of such things, Little Q finds out that string T
occurs as a continuous substring of S′
very often.
Now given strings S
and T
, Little Q has k
questions. Each question is, given L
and R
, Little Q will remove a substring so that the remain parts are S[1..i]
and S[j..n]
, what is the expected times that T
occurs as a continuous substring of S′
if he choose every possible pair of (i,j)(1≤i≤L,R≤j≤n)
equiprobably? Your task is to find the answer E
, and report E×L×(n−R+1)
to him.
Note : When counting occurrences, T
can overlap with each other. 输入描述
The first line of the input contains an integer C(1≤C≤15), denoting the number of test cases.
In each test case, there are 3 integers n,m,k(1≤n≤50000,1≤m≤100,1≤k≤50000) in the first line, denoting the length of S, the length of T and the number of questions.
In the next line, there is a string S consists of n lower-case English letters.
Then in the next line, there is a string T consists of m lower-case English letters.
In the following k lines, there are 2 integers L,R(1≤L<R≤n) in each line, denoting a question.
输出描述
For each question, print a single line containing an integer, denoting the answer.
样例输入
1
8 5 4
iamnotsb
iamsb
4 7
3 7
3 8
2 7
样例输出
1
1
0
0
[提交][状态]
