2 seconds
256 megabytes
standard input
standard output
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 sl,sl+1,…,sr without changing the order.
Each of the occurrences of string a in a string b is a position i (1≤i≤|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[li..ri] .
The first line contains three integer numbers n , m and q (1≤n,m≤103 , 1≤q≤105 ) — 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 li and ri (1≤li≤ri≤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[li..ri] .
10 3 4
codeforces
for
1 3
3 10
5 6
5 7
0
1
0
1
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14
4
0
3
3 5 2
aaa
baaab
1 3
1 1
0
0
In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.
题目大意：就是给两个字符串s t，然后q次查询，给出 [l, r], 问t出现的次数。
刚开始做这道题感觉就是瞎写，没有好好思考，下面给出官方的思路：首先看一下单纯的做法。q次查询，每次从 i 属于 [l, r-m+1] 然后遍历，看是否和t一样。时间复杂度(q*m*n).
注意到t只能从s的n个位置开始，我们可以预处理t出现的位置，然后前缀和维护出现次数，这样的话，每次查询都是O(1).
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f; const int N = + ;
int pre[N]; int main() {
//freopen("in.txt", "r", stdin);
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
string s, t;
cin >> s >> t;
for(int i = ; i < n - m + ; i++) {//从s中找t开始的位置
bool flag = true;
for(int j = ; j < m; j++) {
if(s[i + j] != t[j])
flag = false;
}
pre[i+] = pre[i] + flag;//前缀和
}
for(int i = max(, n - m + ); i < n; i++)//上面终止条件，n-m+1 后面的pre还没有值
pre[i+] = pre[i];
for(int i = ; i < q; i++) {
int l, r;
scanf("%d%d", &l, &r);
l--, r -= m - ;//r -= m-1 变成起始位置（本次次数），l-- 变成上次出现次数
printf("%d\n", l <= r ? pre[r] - pre[l] : );
}
}