CodeForces - 1016B

daybreaking 2018-09-24 原文

You are given two strings $s$

The substring $s [l . . r]$

Each of the occurrences of string $a$

You are asked $q$

Input

The first line contains three integer numbers $n$

The second line is a string $s$

The third line is a string $t$

Each of the next $q$

Output

Print $q$

Examples

Input

10 3 4
codeforces
for
1 3
3 10
5 6
5 7

Output

Input

15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

Output

4
0
3

Input

3 5 2
aaa
baaab
1 3
1 1

Output

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\n",ans);
56     }
57     return 0;
58 }