Problem G. 出现次数
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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\)