Algorithm

B. Segment Occurrences
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1016/problem/B
input
standard input
output
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��,��+1,…,�� without changing the order.

Each of the occurrences of string a� in a string b� is a position i� (1≤i≤|b|−|a|+11≤�≤|�|−|�|+1) such that b[i..i+|a|−1]=a�[�..�+|�|−1]=� (|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]�[��..��].

Input

The first line contains three integer numbers n�, m� and q� (1≤n,m≤1031≤�,�≤103, 1≤q≤1051≤�≤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≤n1≤��≤��≤�) — the arguments for the i�-th query.

Output

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]�[��..��].

Examples
input
Copy
10 3 4
codeforces
for
1 3
3 10
5 6
5 7
output
Copy
0
1
0
1
input
Copy
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14
output
Copy
4
0
3
input
Copy
3 5 2
aaa
baaab
1 3
1 1
output
Copy
0
0
Note

In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e3 + 1;
char s[N], t[N];
int n, m, q;
vector<int> all;

int main() {
  scanf("%d %d %d", &n, &m, &q);
  scanf("%s\n%s", s, t);

  int slen = strlen(s);
  int tlen = strlen(t);

  for(int i = 0; i + tlen - 1 < slen; ++i) {
    bool ok = true;
    for(int j = 0, k = i; j < tlen; ++j, ++k)
      if(s[k] != t[j]) {
        ok = false;
        break;
      }
    if(ok)
      all.push_back(i);
  }

  for(int i = 0, a, b; i < q; ++i) {
    int res = 0;
    scanf("%d %d", &a, &b);
    --a, --b;
    for(int j = 0; j < all.size(); ++j)
      if(all[j] >= a && all[j] + tlen - 1 <= b)
        ++res;
    printf("%d\n", res);
  }

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
10 3 4
codeforces
for
1 3
3 10
5 6
5 7

Output

x
–
+
cmd
0
1
0
1
Advertisements

Demonstration

Codeforces Solution-B. Segment Occurrences-Solution in C, C++, Java, Python,Segment Occurrences,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+