Problem G. 出现次数

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 ,所以 baabacabadabacaba 中作为子串出现了 \(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\)

信息

ID
1388
难度
7
分类
(无)
标签
(无)
递交数
170
已通过
32
通过率
19%
被复制
1
上传者

相关

在下列比赛中:

2022年暑期算法队集训赛