You are given two strings ss and tt, both consisting only of lowercase Latin letters.
The substring s[l..r]s[l..r] is the string which is obtained by taking characters sl,sl+1,…,srsl,sl+1,…,sr without changing the order.
Each of the occurrences of string aa in a string bb is a position ii (1≤i≤|b|−|a|+11≤i≤|b|−|a|+1) such that b[i..i+|a|−1]=ab[i..i+|a|−1]=a (|a||a| is the length of string aa).
You are asked qq queries: for the ii-th query you are required to calculate the number of occurrences of string tt in a substring s[li..ri]s[li..ri].
Input
The first line contains three integer numbers nn, mm and qq (1≤n,m≤1031≤n,m≤103, 1≤q≤1051≤q≤105) — the length of string ss, the length of string tt and the number of queries, respectively.
The second line is a string ss (|s|=n|s|=n), consisting only of lowercase Latin letters.
The third line is a string tt (|t|=m|t|=m), consisting only of lowercase Latin letters.
Each of the next qq lines contains two integer numbers lili and riri (1≤li≤ri≤n1≤li≤ri≤n) — the arguments for the ii-th query.
Output
Print qq lines — the ii-th line should contain the answer to the ii-th query, that is the number of occurrences of string tt in a substring s[li..ri]s[li..ri].
Examples
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
Note
In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.
刚开始不会做，是因为只想到了用前缀和，没想到应该怎么去用，根据题意，只有当string t 全部在在所查区间的时候，答案才加一，
所以说如果从查询区间的头部向后遍历的话，不但要知道从哪个字母开始，还要判断字符串t何时结束，前缀和不太好维护。
因此，我们从查询区间的尾部向前遍历，只要找到字符串t结束的地方，只需要判断字符串t的开头是否在查询区间之内即可，这样的前缀和容易维护。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<deque> 10 #include<map> 11 #include<iostream> 12 using namespace std; 13 typedef long long LL; 14 const double pi=acos(-1.0); 15 const double e=exp(1); 16 const int N = 10; 17 18 char con[1009],sub[1009]; 19 int check[1009]; 20 int main() 21 { 22 int i,p,j,n,m,q; 23 int flag,a,b,ans; 24 scanf("%d%d%d",&n,&m,&q); 25 scanf(" %s",con+1); 26 scanf(" %s",sub+1); 27 28 for(i=1;i<=n-m+1;i++) 29 { 30 p=1; 31 flag=0; 32 for(j=i;j<=i+m;j++) 33 { 34 if(p>m) 35 { 36 flag=1; 37 break; 38 } 39 if(con[j]!=sub[p]) 40 break; 41 p++; 42 } 43 if(flag==1) 44 check[j-1]=1; 45 } 46 for(i=1;i<=q;i++) 47 { 48 ans=0; 49 scanf("%d%d",&a,&b); 50 for(j=a;j<=b;j++) 51 { 52 if(check[j]==1&&j-(m-1)>=a) 53 ans++; 54 } 55 printf("%d ",ans); 56 } 57 return 0; 58 }