Problem G. 出现次数

时间限制：2s
空间限制：256MB

题目描述

给定一个长度为 \(n\) 的字符串 \(S=s_{1}s_{2}...s_n\) 以及一个长度为 \(m\) 的字符串 \(T=t_1t_2...t_m\)。

两个字符串都由小写字母构成。

用 \(s[l,r]\) 来表示字符串 \(S\) 的子串 \(s_{l}s_{l+1}...s_r\) 。

有 \(q\) 个询问，每个询问给出两个整数 \(l_i,r_i（1 \leq l_i \leq r_i \leq n）\) ，请你计算字符串 \(T\) 在 \(s[l_i,r_i]\) 中作为子串出现了多少次。

例如，字符串 abacabadabacaba 中共包含\(4\)个子串 ba ，所以 ba 在 abacabadabacaba 中作为子串出现了 \(4\) 次。

输入格式

第一行包含三个整数\(n,m,q\)。

第二行包含一个长度为\(n\)的由小写字母构成的字符串\(S\)。

第三行包含一个长度为\(m\)的由小写字母构成的字符串\(T\)。

接下来\(q\)行，每行包含两个整数\(l_i,r_i\)。

输出格式

每个询问输出一行答案，一个整数，表示出现次数。

样例输入1

15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

样例输出1

4
0
3

样例输入2

3 5 2
aaa
baaab
1 3
1 1

样例输出2

0
0

数据范围

对于50%的数据，\(1 \leq n,m \leq 100, 1 \leq q \leq 10000\),
对于100%的数据，\(1 \leq n,m \leq 5000, 1 \leq q \leq 3 \times 10^5, 1 \leq l_i \leq r_i \leq n\)