305368: CF1016B. Segment Occurrences
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Segment Occurrences
题意翻译
有长度为$n$的串$a$,长度为$m$的串$b$,共$q$次询问,每次询问$a$在$l$到$r$区间中有多少个$b$。题目描述
You are given two strings $ s $ and $ t $ , both consisting only of lowercase Latin letters. The substring $ s[l..r] $ is the string which is obtained by taking characters $ s_l, s_{l + 1}, \dots, s_r $ without changing the order. Each of the occurrences of string $ a $ in a string $ b $ is a position $ i $ ( $ 1 \le i \le |b| - |a| + 1 $ ) such that $ b[i..i + |a| - 1] = a $ ( $ |a| $ is the length of string $ a $ ). You are asked $ q $ queries: for the $ i $ -th query you are required to calculate the number of occurrences of string $ t $ in a substring $ s[l_i..r_i] $ .输入输出格式
输入格式
The first line contains three integer numbers $ n $ , $ m $ and $ q $ ( $ 1 \le n, m \le 10^3 $ , $ 1 \le q \le 10^5 $ ) — the length of string $ s $ , the length of string $ t $ and the number of queries, respectively. The second line is a string $ s $ ( $ |s| = n $ ), consisting only of lowercase Latin letters. The third line is a string $ t $ ( $ |t| = m $ ), consisting only of lowercase Latin letters. Each of the next $ q $ lines contains two integer numbers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the arguments for the $ i $ -th query.
输出格式
Print $ q $ lines — the $ i $ -th line should contain the answer to the $ i $ -th query, that is the number of occurrences of string $ t $ in a substring $ s[l_i..r_i] $ .
输入输出样例
输入样例 #1
10 3 4
codeforces
for
1 3
3 10
5 6
5 7
输出样例 #1
0
1
0
1
输入样例 #2
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14
输出样例 #2
4
0
3
输入样例 #3
3 5 2
aaa
baaab
1 3
1 1
输出样例 #3
0
0