#include <bits/stdc++.h>
using namespace std;
char s[100005], t[100005];
int Q, m, n, l1, l2;
int sum[100005], fr[100005], ma[100005];
void init() {
  int i, np;
  scanf("%d%d%d", &l1, &l2, &Q);
  scanf("%s", s);
  scanf("%s", t);
  for (i = l1; i > 0; i--) s[i] = s[i - 1];
  for (i = l2; i > 0; i--) t[i] = t[i - 1];
  fr[1] = 0;
  for (i = 2; i <= l2; i++) {
    np = fr[i - 1];
    while (t[i] != t[np + 1] && np) np = fr[np];
    if (t[i] == t[np + 1])
      fr[i] = np + 1;
    else
      fr[i] = 0;
  }
  t[l2 + 1] = '&';
  ma[0] = 0;
  for (i = 1; i <= l1; i++) {
    np = ma[i - 1];
    while (np && s[i] != t[np + 1]) np = fr[np];
    if (s[i] == t[np + 1])
      ma[i] = np + 1;
    else
      ma[i] = 0;
  }
  sum[0] = 0;
  for (i = 1; i <= l1; i++) sum[i] = sum[i - 1] + (ma[i] == l2);
}
int main() {
  int i, l, r;
  init();
  for (i = 1; i <= Q; i++) {
    scanf("%d%d", &l, &r);
    if (r - l + 1 < l2) {
      printf("0\n");
      continue;
    }
    printf("%d\n", max(0, sum[r] - sum[l + l2 - 2]));
  }
  return 0;
}
