
ZOJ Problem Set  4030
Tired of solving mathematical equations, DreamGrid starts to solve equations related to strings: for two strings $x$ and $y$ with the same length consisting of lowercase English letters, calculate $f(x,y,n)$, which is defined as the number of nonempty strings $z$ consisting of lowercase English letters such that $xz=zy$ and the length of $z$ does not exceed $n$. DreamGrid has two strings $s=s_{1}s_{2}\dots s_{n}$ and $t=t_{1}t_{2}\dots t_{m}$. He would like to ask several questions about the value of $f(t, s[x..(x+m1)], y)$, where $s[x..(x+m1)]$ is the substring of $s$ starting from $s_x$ with length $m$ and $y$ is a given number. InputThere are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains three integers $n$ and $m$ and $q$ ($1 \le n, m, q \le 10^5, m \le n$)  the length of $s$, the length of $t$ and the number of questions. The second line contains $n$ lowercase English letters denoting the string $s$. The third line contains $m$ lowercase English letters denoting the string $t$. Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n + 1  m, 1 \le y_i \le 10^{18}$) denoting the $i$th question. It is guaranteed that neither the sum of all $n$ nor the sum of all $q$ exceeds $10^6$. OutputFor each question, output an integer denoting the answer. Sample Input1 4 2 3 abcd ba 1 2 2 2 3 2 Sample Output1 0 0 Author: LIN, Xi Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 