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 $s_l, s_{l + 1}, \dots, s_r$ without changing the order.

Each of the occurrences of string $a$ in a string $b$ is a position $i$ ($1 \le i \le |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[l_i..r_i]$.


-----Input-----

The first line contains three integer numbers $n$, $m$ and $q$ ($1 \le n, m \le 10^3$, $1 \le q \le 10^5$) — 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 $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — 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[l_i..r_i]$.


-----Examples-----
Input
10 3 4
codeforces
for
1 3
3 10
5 6
5 7

Output
0
1
0
1

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.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
import sys

def main():
	(n, m, q) = list(map(int, input().strip().split()))
	s = input()
	t = input()
	pos = []
	for i in range(len(s)):
		if i + len(t) <= len(s) and s[i:i + len(t)] == t:
			pos.append(1)
		else:
			pos.append(0)
	sum = [0]
	for i in range(len(pos)):
		sum.append(sum[-1] + pos[i])
	for _ in range(q):
		(l, r) = list(map(int, input().strip().split()))
		r = r - len(t) + 1
		l -= 1
		if l < r:
			print(sum[r] - sum[l])
		else:
			print(0)
	return 0

def test(i):
	with open('test_{}.txt'.format(i)) as fin:
		sys.stdin = fin
		main()

def __starting_point():
	return main()
__starting_point()


from sys import stdin, stdout
from bisect import bisect_left

def main():
	(n, m, q) = map(int, stdin.readline().split())
	s = stdin.readline()
	t = stdin.readline()
	start = []
	end = []
	for i in range(n - m + 1):
		j = 0
		while j < m and s[i + j] == t[j]:
			j += 1
		if j == m:
			start.append(i)
			end.append(i + j - 1)
	len_start = len(start)
	len_end = len(end)
	for _ in range(q):
		(l, r) = map(int, stdin.readline().split())
		l -= 1
		r -= 1
		if not start:
			stdout.write('%d\n' % 0)
			continue
		x = bisect_left(start, l)
		y = bisect_left(end, r)
		if x == len_end:
			stdout.write('%d\n' % 0)
			continue
		if y == len_end:
			stdout.write('%d\n' % max(0, y - x))
			continue
		if end[y] == r:
			stdout.write('%d\n' % max(0, y - x + 1))
			continue
		else:
			stdout.write('%d\n' % max(0, y - x))
main()


from itertools import accumulate
from sys import stdin
all_in = list((el.rstrip('\n') for el in stdin.readlines()))
(n, m, q) = map(int, all_in[0].split())
s = all_in[1]
t = all_in[2]
l_r = [tuple(map(int, el.split())) for el in all_in[3:]]
in_ = [int(t == s[i:i + m]) for i in range(n - m + 1)]
acc = [0] + list(accumulate(in_))
ans = list()
for (a, b) in l_r:
	if b - a + 1 < m:
		ans.append(0)
		continue
	ans.append(acc[max(0, b - m + 1)] - acc[a - 1])
print('\n'.join(map(str, ans)))


import itertools as it
(n, m, q) = map(int, input().split())
(s, t) = (input(), input())
p = [int(s[i:i + len(t)] == t) for i in range(0, n - len(t) + 1)] + [0] * (len(t) - 1)
p = [0] + list(it.accumulate(p))
for _ in range(q):
	(left, right) = map(int, input().split())
	if right - left + 1 < len(t):
		print(0)
	else:
		print(p[right - len(t) + 1] - p[left - 1])


def coun(s, t):
	d = 0
	for i in range(len(s) - len(t) + 1):
		if s[i:i + len(t)] == t:
			d += 1
	return d
(n, m, q) = list(map(int, input().split()))
s = input()
t = input()
x = [0]
for j in range(n):
	x.append(coun(s[:j + 1], t))
for i in range(q):
	(l, r) = list(map(int, input().split()))
	r += 1
	if m <= r - l:
		print(x[r - 1] - x[max(0, l + m - 2)])
	else:
		print(0)


(n, m, q) = [int(x) for x in input().split()]
sn = input()
sm = input()

def eq(i):
	for j in range(m):
		if sn[i + j] != sm[j]:
			return False
	return True
re = [0] * n
for i in range(n - m + 1):
	if eq(i):
		re[i] = 1
for i in range(1, n):
	re[i] += re[i - 1]
for i in range(q):
	(l, r) = [int(x) - 1 for x in input().split()]
	if r - l + 1 < m:
		print(0)
		continue
	if l == 0:
		print(re[r - m + 1])
	else:
		print(re[r - m + 1] - re[l - 1])


def subamount(l, r):
	if r - l < m - 1:
		return 0
	elif m + l - 2 < 0:
		return pr[r] - 0
	return pr[r] - pr[m + l - 2]
(n, m, q) = map(int, input().split())
s = input()
t = input()
pr = [0] * n
if m <= n:
	pr[m - 1] = int(t == s[:m])
	for i in range(m, n):
		pr[i] = pr[i - 1] + (t == s[i - m + 1:i + 1])
for _ in range(q):
	(l, r) = map(int, input().split())
	print(subamount(l - 1, r - 1))


(n, m, k) = map(int, input().split())
a = list(input())
b = list(input())
l = []
j = 0
while j < n - m + 1:
	if j + m <= n:
		if a[j:j + m] == b:
			l.append(j)
	else:
		break
	j += 1
for i in range(k):
	(x, y) = map(int, input().split())
	c = 0
	x -= 1
	y -= 1
	for i in range(len(l)):
		if l[i] >= x and l[i] + m - 1 <= y:
			c += 1
	print(c)


(n, m, q) = map(int, input().split())
s = input()
t = input()
dp = [0] * (n + 1)
found_so_far = 0
for i in range(n - m + 1):
	if s[i:i + m] == t:
		found_so_far += 1
	dp[i + m] = found_so_far
for _ in range(q):
	(a, b) = map(int, input().split())
	if b - a + 1 < m:
		print(0)
	else:
		print(dp[b] - dp[a + m - 2])


from collections import defaultdict
(n, m, q) = [int(i) for i in input().split()]
s = input()
t = input()
x = []
sums = [0 for i in range(n)]
for i in range(q):
	x.append([int(i) - 1 for i in input().split()])
for i in range(n):
	if i - m + 1 >= 0:
		if s[i - m + 1:i + 1] == t:
			sums[i] += 1
	if i != 0:
		sums[i] += sums[i - 1]
for i in x:
	if abs(i[1] - i[0]) + 1 < m:
		print(0)
	else:
		l = sums[i[1]]
		if i[0] + m - 2 < 0:
			r = 0
		else:
			r = sums[min(n - 1, i[0] + m - 2)]
		print(l - r)


from sys import stdin

def main():
	(n, m, q) = [int(s) for s in stdin.readline().split(' ')]
	s = stdin.readline().strip()
	t = stdin.readline().strip()
	queries = []
	for line in range(0, q):
		queries.append([int(s) for s in stdin.readline().split(' ')])
	acum = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		acum[i] = acum[i - 1]
		if checkIndex(i, s, t, n, m):
			acum[i] += 1
	for query in queries:
		if query[1] - query[0] + 1 < m:
			print(0)
		else:
			print(acum[query[1] - m + 1] - acum[query[0] - 1])

def checkIndex(fromIndex, s, t, n, m):
	valid = True
	if n - fromIndex + 1 < m:
		return False
	for i in range(0, m):
		valid = valid and t[i] == s[fromIndex + i - 1]
		if not valid:
			break
	return valid
main()


from bisect import bisect_left, bisect_right
(n, m, q) = list(map(int, input().split()))
(s, t) = (input(), input())
x = []
for i in range(len(s) - len(t) + 1):
	if s[i:i + len(t)] == t:
		x.append(i)
sx = set(x)
for _ in range(q):
	(l, r) = list(map(int, input().split()))
	if r - l + 1 < len(t):
		print(0)
		continue
	i = bisect_right(x, l - 1)
	j = bisect_left(x, r - len(t))
	if l - 1 in sx:
		i -= 1
	if r - len(t) not in sx:
		j -= 1
	print(j - i + 1)


from bisect import bisect_left, bisect_right

def main():
	(n, m, q) = list(map(int, input().split(' ')))
	s = input()
	t = input()
	ps = []
	for i in range(n - m + 1):
		if t == s[i:i + m]:
			ps.append(i)
	ans = []
	for _ in range(q):
		(l, r) = list(map(int, input().split(' ')))
		(l, r) = (l - 1, r - 1)
		i = bisect_left(ps, l)
		j = bisect_right(ps, r - m + 1)
		ans.append(max(j - i, 0))
	for x in ans:
		print(x)

def __starting_point():
	main()
__starting_point()


(n, m, q) = map(int, input().split())
s = input()
t = input()
a = [0] * (1000 + 7)
b = [0] * (1000 + 7)
for i in range(n - m + 1):
	fl = 1
	for j in range(m):
		if s[i + j] != t[j]:
			fl = 0
			break
	b[i] = fl
	a[i + 1] = a[i] + b[i]
for i in range(max(0, n - m + 1), n):
	a[i + 1] = a[i]
while q > 0:
	q -= 1
	(l, r) = map(int, input().split())
	l -= 1
	r -= m - 1
	if r < l:
		print(0)
	else:
		print(a[r] - a[l])


(a, b, c) = map(int, input().split())
s1 = input()
s2 = input()
coun = [0 for i in range(a + 5)]
if a >= b:
	for i in range(a - b + 1):
		coun[i + 1] = coun[i] + (s1[i:i + b] == s2)
	for i in range(a - b + 1, a + 5):
		if coun[i] == 0:
			coun[i] = coun[i - 1]
	for i in range(c):
		(x, y) = map(int, input().split())
		if y - x + 1 < b:
			print('0')
		else:
			print(coun[y - b + 1] - coun[x - 1])
else:
	print('0\n' * c)


(n, m, q) = map(int, input().split())
s = input()
t = input()
c = [0 for i in range(n + 1)]
b = 0
for i in range(n - m + 1):
	if s[i:i + m] == t:
		c[i + 1] = 1
for i in range(1, n + 1):
	c[i] += c[i - 1]
for i in range(q):
	(l, r) = map(int, input().split())
	if r - l + 1 < m:
		print(0)
	elif l == 1:
		print(c[r - m + 1])
	else:
		print(c[r - m + 1] - c[l - 1])


a1 = list(map(int, input().split(' ')[:3]))
bigString = input()
littleString = input()
all = 0
left = [0] * len(bigString)
right = [0] * len(bigString)
leftCount = 0
rightCount = 0
for i in range(len(bigString)):
	left[i] = leftCount
	if bigString.find(littleString, i, i + len(littleString)) != -1:
		leftCount += 1
for i in range(len(bigString) - 1, -1, -1):
	right[i] = rightCount
	if bigString.find(littleString, i - len(littleString) + 1, i + 1) != -1:
		rightCount += 1
for i in range(len(bigString)):
	if bigString.find(littleString, i, i + len(littleString)) != -1:
		all += 1
for s in range(a1[2]):
	a2 = list(map(int, input().split(' ')[:2]))
	a2[0] -= 1
	a2[1] -= 1
	if a2[1] - a2[0] < len(littleString) - 1:
		print(0)
	else:
		result = all - right[a2[1]] - left[a2[0]]
		print(result)


(n, m, q) = map(int, input().split())
s = input()
t = input()
res = []
for i in range(n - m + 1):
	if s[i:i + m] == t:
		e = (i, i + m - 1)
		res.append(e)
for i in range(q):
	(li, ri) = map(int, input().split())
	k = 0
	for (t, p) in res:
		if t >= li - 1 and p <= ri - 1:
			k += 1
	print(k)


import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
(n, m, q) = get_ints()
s = input()
p = input()
ans = []
i = 0
count = 0
while True:
	si = s.find(p, i)
	if si != -1:
		ans += [count] * (si - i + 1)
		count += 1
		i = si + 1
	else:
		ans += [count] * (n - i + 2)
		break
out = []
for i in range(q):
	(a, b) = get_ints()
	a -= 1
	b -= m - 1
	out.append(ans[b] - ans[a] if b >= a else 0)
print(*out, sep='\n')


(n, m, q) = list(map(int, input().strip().split()))
s = input()
t = input()
locs = []
for i in range(n):
	if i + m <= n and s[i:i + m] == t:
		locs.append(i)

def find_max(nums, target):
	(l, r) = (0, len(nums) - 1)
	while l < r:
		mid = (l + r) // 2
		if nums[mid] >= target:
			r = mid
		else:
			l = mid + 1
	if nums[l] >= target:
		return l
	else:
		return len(nums)

def helper(l, r, nums):
	if len(nums) == 0:
		return 0
	x = find_max(nums, l)
	y = find_max(nums, r)
	if y >= len(nums) or nums[y] > r:
		return y - x
	else:
		return y - x + 1
for i in range(q):
	(l, r) = list(map(int, input().strip().split()))
	l -= 1
	r -= 1
	if r - m + 1 < l:
		print(0)
	else:
		res = helper(l, r - m + 1, locs)
		print(res)


R = lambda : map(int, input().split())
(n, m, q) = R()
(s, t) = (input(), input())
a = [0] * 1005
for i in range(n):
	a[i + 2] = a[i + 1] + (s[i:i + m] == t)
for _ in [0] * q:
	(l, r) = R()
	print(a[max(l, r - m + 2)] - a[l])


def count_overlapping_substrings(haystack, needle):
	count = 0
	i = -1
	while True:
		i = haystack.find(needle, i + 1)
		if i == -1:
			return count
		left.append(i)
		right.append(i + len(needle) - 1)
		count += 1

def bin_search(lst, x):
	lower_bound = 0
	upper_bound = len(lst) - 1
	while lower_bound != upper_bound:
		compared_value = (lower_bound + upper_bound) // 2
		if x == lst[compared_value]:
			return compared_value
		elif x < lst[compared_value]:
			upper_bound = compared_value
		else:
			lower_bound = compared_value + 1
	return lower_bound
(n, m, q) = map(int, input().split())
s1 = input()
s2 = input()
right = []
left = []
count_overlapping_substrings(s1, s2)
for i in range(q):
	(l, r) = map(int, input().split())
	if right == []:
		print(0)
		continue
	a = bin_search(left, l - 1)
	b = bin_search(right, r - 1)
	if left[a] < l - 1:
		a += 1
	if right[b] > r - 1:
		b -= 1
	if a > b:
		print(0)
	else:
		print(b - a + 1)


(a, b, n) = map(int, input().split())
s = input()
t = input()
pre = [0] * 100860

def pre_cnt(s1, s2):
	for i in range(0, len(s1) - len(s2) + 1):
		if s1[i:i + len(s2)] == s2:
			pre[i + 1] = pre[i] + 1
		else:
			pre[i + 1] = pre[i]
pre_cnt(s, t)
while n != 0:
	n -= 1
	(a, b) = map(int, input().split())
	ans = pre[b - len(t) + 1] - pre[a - 1]
	if a - 1 > b - len(t) + 1:
		ans = 0
	print(ans)


from sys import stdin, stdout

def rint():
	return map(int, stdin.readline().split())
(n, m, q) = rint()
s = input()
t = input()
occur_in_s = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	if i + m > n:
		occur_in_s[i] = occur_in_s[i + 1]
		continue
	if s[i:i + m] == t:
		occur_in_s[i] = occur_in_s[i + 1] + 1
	else:
		occur_in_s[i] = occur_in_s[i + 1]
for i in range(q):
	(l, r) = rint()
	l -= 1
	r -= 1
	if r - l + 1 < m:
		print(0)
	else:
		print(occur_in_s[l] - occur_in_s[r - m + 2])


from itertools import accumulate
(n, m, q) = map(int, input().split())
a = input()
b = input()
acc = [0] + list(accumulate([int(a[i:i + m] == b) for i in range(n - m + 1)]))
for i in range(q):
	(x, y) = map(int, input().split())
	if n < m:
		print(0)
	else:
		print(max(0, acc[max(y - m + 1, 0)] - acc[min(x - 1, n - m + 1)]))


(n, m, q) = map(int, input().split())
s = str(input())
t = str(input())
ans = list()
if n >= m:
	buf = ''
	for i in range(0, m - 1):
		buf += s[i]
	for i in range(m - 1, n):
		buf += s[i]
		ok = 1
		for j in range(m):
			ok &= buf[i - m + 1 + j] == t[j]
		ans.append(ok)
while len(ans) < n:
	ans.append(0)
pref = list()
for i in range(n):
	if i == 0:
		pref.append(ans[0])
	else:
		pref.append(pref[i - 1] + ans[i])
for _ in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	if r - l + 1 < m:
		print(0)
	elif l == 0:
		print(pref[r - m + 1])
	else:
		print(pref[r - m + 1] - pref[l - 1])


[n, m, q] = input().split()
n = int(n)
m = int(m)
q = int(q)
s = input()
t = input()
a = [0 for i in range(n + 5)]
for i in range(0, n - m + 1):
	if s[i:i + m] == t:
		a[i + 1] = 1
for i in range(1, n + 3):
	a[i] += a[i - 1]
for i in range(q):
	[l, r] = input().split()
	l = int(l)
	r = int(r)
	if r - l + 1 < m:
		print(0)
	else:
		print(a[r - m + 1] - a[l - 1])


import sys

def mapi():
	return map(int, input().split())

def maps():
	return map(str, input().split())
(n, m, q) = mapi()
s = input().strip()
t = input().strip()
i = 0
j = m
mp = {}
pf = [0]
for i in range(n - m + 1):
	if s[i:i + m] == t:
		pf.append(pf[-1] + 1)
	else:
		pf.append(pf[-1])
for i in range(max(0, n - m + 1), n):
	pf.append(pf[-1])
for _ in range(q):
	(l, r) = mapi()
	l = l - 1
	r = r - m + 1
	if l <= r:
		print(pf[r] - pf[l])
	else:
		print(0)


3

def calc(l, r, layers, li):
	if r - l == 1:
		return layers[li][l]
	xl = l
	if l % 2 == 1:
		xl -= 1
	xr = r
	if r % 2 == 1:
		xr += 1
	ans = calc(xl // 2, xr // 2, layers, li + 1)
	if xl != l:
		ans -= layers[li][xl]
	if xr != r:
		ans -= layers[li][xr - 1]
	return ans

def solve(N, M, Q, S, T, A):
	base = [0] * N
	i = 0
	while True:
		try:
			i = S.index(T, i)
			base[i] = 1
			i += 1
		except ValueError:
			break
	layers = [base]
	while len(layers[-1]) > 1:
		prev = layers[-1]
		if len(prev) % 2 == 1:
			prev.append(0)
		layer = []
		for i in range(len(prev) // 2):
			layer.append(prev[2 * i] + prev[2 * i + 1])
		layers.append(layer)
	ans = []
	for (l, r) in A:
		l -= 1
		r -= M - 1
		if r <= l:
			ans.append(0)
			continue
		ans.append(calc(l, r, layers, 0))
	return ans

def main():
	(N, M, Q) = [int(e) for e in input().split(' ')]
	S = input()
	T = input()
	A = [map(int, input().split(' ')) for _ in range(Q)]
	assert len(S) == N
	assert len(T) == M
	print(*solve(N, M, Q, S, T, A), sep='\n')

def __starting_point():
	main()
__starting_point()


import re, bisect
(n, m, q) = [int(v) for v in input().split()]
s = input().strip()
t = input().strip()
starts = [m.start() for m in re.finditer('(?=%s)' % t, s)]
for _ in range(q):
	(l, r) = [int(v) for v in input().split()]
	if r - l + 1 < len(t):
		print(0)
	else:
		print(bisect.bisect_right(starts, r - len(t)) - bisect.bisect_left(starts, l - 1))


from sys import stdin, stdout
(n, m, q) = map(int, input().split())
s = input()
t = input()
x = 0
dp1 = []
while x < n:
	if s[x - m + 1:x + 1] == t:
		dp1.append(1)
	else:
		dp1.append(0)
	x += 1
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	acum = 0
	for j in range(i, n):
		if dp1[j] != 0 and j - m + 1 >= i:
			acum += dp1[j]
		dp[i][j] = acum
ans = ''
for i in range(q):
	(l, r) = map(int, input().split())
	ans += str(dp[l - 1][r - 1]) + chr(10)
stdout.write(ans)


(n, m, q) = [int(i) for i in input().split()]
s = input()
t = input()
positions = ''
for i in range(n - m + 1):
	if s[i:i + m] == t:
		positions += '1'
	else:
		positions += '0'
for i in range(q):
	(l, r) = map(int, input().split())
	if r - l + 1 >= m:
		print(positions[l - 1:r - m + 1].count('1'))
	else:
		print(0)


(n, m, q) = list(map(int, input().split()))
a = list(input())
b = list(input())
s = 0
starts = []
arr = []
for i in range(len(a) - len(b) + 1):
	if a[i:i + len(b)] == b:
		arr.append(1)
		s += 1
	else:
		arr.append(0)
	starts.append(s)
for i in range(q):
	(l, r) = list(map(int, input().split()))
	if r - l + 1 < len(b):
		print(0)
		continue
	print(starts[r - len(b)] - starts[l - 1] + arr[l - 1])


(n, m, q) = map(int, input().split())
(s, t) = (input(), input())
a = [0, 0]
b = 0
for i in range(n):
	b += s[i:i + m] == t
	a += [b]
for _ in [0] * q:
	(l, r) = map(int, input().split())
	print(a[max(l, r - m + 2)] - a[l])


from collections import Counter

def main():
	(n, m, q) = [int(c) for c in input().split()]
	s = input()
	t = input()
	ok = []
	pr = [0]
	for i in range(0, n):
		ok.append(1 if t == s[i:i + m] else 0)
		pr.append(pr[-1] + ok[-1])
	res = []
	for i in range(q):
		(li, ri) = [int(c) for c in input().split()]
		res.append(0 if ri - li + 1 < m else pr[ri - m + 1] - pr[li - 1])
	for e in res:
		print(e)
main()


(n, m, q) = [int(i) for i in input().split()]
s = list(input())
t = list(input())
lt = len(t)
ls = len(s)
start = []
for i in range(ls - lt + 1):
	j = i
	count = 0
	while s[j] == t[count]:
		j += 1
		count += 1
		if count >= lt:
			break
	if count == lt:
		start.append(i + 1)
start += [n + 1]
for i in range(q):
	(l, r) = [int(j) for j in input().split()]
	r -= lt - 1
	if l > r:
		print(0)
		continue
	f = False
	for j in range(len(start)):
		if f == False and start[j] >= l:
			f = True
			begin = j
		if f and start[j] > r:
			end = j
			break
	print(end - begin)


(n, m, q) = map(int, input().split())
s = input()
t = input()
a = [0] * n
for i in range(n - m + 1):
	if s[i:i + m] == t:
		a[i] = 1
for i in range(q):
	(u, v) = map(int, input().split())
	l = u - 1
	r = v - m
	c = sum(a[l:r + 1]) if l <= r else 0
	print(c)


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
t = 1
for tt in range(t):
	(n, m, qq) = invr()
	a = insr()
	b = insr()
	q = [[0] * len(a) for i in range(len(a))]
	for i in range(len(a)):
		w = [j for j in range(len(a[i:])) if a[i:].startswith(b, j)]
		for j in range(len(w)):
			w[j] = w[j] + m - 1 + i
		w.reverse()
		c = 0
		for j in range(len(a)):
			if w and j == w[-1]:
				c = c + 1
				w.pop()
			q[i][j] = c
	for i in range(qq):
		(l, r) = invr()
		print(q[l - 1][r - 1])


(n, m, q) = list(map(int, input().split()))
s = list(input())
t = list(input())
a = [list(map(int, input().split())) for i in range(q)]
if n < m:
	for i in range(q):
		print(0)
	return
res = [0] * (n - m + 1)
for i in range(n - m + 1):
	if s[i:i + m] == t:
		res[i] = 1
for u in range(q):
	l = a[u][0]
	r = a[u][1]
	ans = 0
	for y in range(l - 1, r - m + 1):
		if res[y] == 1:
			ans += 1
	print(ans)


def mmhaxor(n, m, q, s, t):
	a = [0] * 10000
	for i in range(n):
		a[i + 2] = a[i + 1] + (s[i:i + m] == t)
	for i in range(q):
		ans = 0
		(l, r) = map(int, input().split())
		print(a[max(r - m + 2, l)] - a[l])
(n, m, q) = map(int, input().split())
s = input()
t = input()
mmhaxor(n, m, q, s, t)


import bisect
(n, m, q) = map(int, input().split())
s = input()
t = input()

def find_substring(substring, string):
	indices = []
	index = -1
	while True:
		index = string.find(substring, index + 1)
		if index == -1:
			break
		indices.append(index + 1)
	return indices
l = find_substring(t, s)
ans = []
d = 0
f = 0
while q:
	(a, b) = map(int, input().split())
	d = 0
	if b - a + 1 >= len(t):
		b = b - len(t) + 1
		d = bisect.bisect_left(l, a)
		f = bisect.bisect_right(l, b)
		ans.append(str(f - d))
	else:
		ans.append('0')
	q = q - 1
print('\n'.join(ans))


(lena, lenb, noq) = [int(x) for x in input().split()]
a = input()
b = input()
cnts = [0] * lena
for i in range(lena):
	cnts[i] += a[i:i + lenb] == b
for i in range(noq):
	(s, e) = [int(x) for x in input().split()]
	(s, e) = (s - 1, e - lenb + 1)
	ans = 0
	if s < e:
		ans = sum(cnts[s:e])
	print(ans)


(n, m, q) = [int(i) for i in input().split()]
S = input()
T = input()
A = [[int(i) for i in input().split()] for j in range(q)]
s = []
for i in range(len(S)):
	if S[i:i + len(T)] == T:
		s.append(1)
	else:
		s.append(0)
csum = [0]
for s_ in s:
	csum.append(csum[-1] + s_)
for (a, b) in A:
	print(csum[max(a - 1, b - len(T) + 1)] - csum[a - 1])


(n, m, q) = map(int, input().split())
s = input()
t = input()
x = 0
dp1 = [0 for i in range(n)]
while x < n:
	if s[x - m + 1:x + 1] == t:
		dp1[x] = 1
	else:
		dp1[x] = 0
	x += 1
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	acum = 0
	for j in range(i, n):
		if dp1[j] != 0 and j - m + 1 >= i:
			acum += dp1[j]
		dp[i][j] = acum
ans = ''
for i in range(q):
	(l, r) = map(int, input().split())
	ans += str(dp[l - 1][r - 1]) + chr(10)
print(ans)


(n, m, q) = map(int, input().split())
s = input()
t = input()
arr = [0] * 1008
arr2 = [0] * 1008
for i in range(n - m + 1):
	fl = 1
	for j in range(m):
		if s[i + j] != t[j]:
			fl = 0
	arr2[i] = fl
	arr[i + 1] = arr[i] + arr2[i]
for i in range(max(0, n - m + 1), n):
	arr[i + 1] = arr[i]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= m - 1
	if r >= l:
		print(arr[r] - arr[l])
	else:
		print(0)


def main():
	(n, m, q) = [int(x) for x in input().split()]
	s = input()
	t = input()
	st1 = [0 for i in range(n + 1)]
	st2 = [0 for i in range(n + 1)]
	for i in range(m, n + 1):
		if t == s[i - m:i]:
			st1[i - m + 1] = 1
			st2[i - 1] = 1
	for i in range(1, n + 1):
		st1[i] = st1[i - 1] + st1[i]
		st2[i] = st2[i - 1] + st2[i]
	for i in range(q):
		(l, r) = [int(x) for x in input().split()]
		if r - l < m - 1:
			print(0)
		else:
			print(st1[n] - st1[l - 1] - (st2[n] - st2[r - 1]))
main()


(n, m, q) = map(int, input().split())
s = input()
t = input()
nex = -1
i = 0
ans = [0] * n
while i < n:
	if s[i] == t[0]:
		nex = -1
		start = i
		i += 1
		j = 1
		flag = False
		while i < n and j < m:
			if not flag:
				if s[i] == t[0]:
					nex = i
					flag = True
			if s[i] != t[j]:
				break
			i += 1
			j += 1
		if j == m:
			ans[start] = 1
		if nex != -1:
			i = nex
	else:
		i += 1
ans.insert(0, 0)
for i in range(1, n + 1):
	ans[i] = ans[i] + ans[i - 1]
for _ in range(q):
	(l, r) = map(int, input().split())
	if r - l + 1 >= m:
		print(ans[r - m + 1] - ans[l - 1])
	else:
		print('0')


from sys import stdin, stdout
from math import gcd
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')

def solve():
	(a, b, q) = mp()
	s = input()
	t = input()
	dp = [0]
	for i in range(a - b + 1):
		if s[i:i + b] == t:
			dp.append(dp[-1] + 1)
		else:
			dp.append(dp[-1])
	for i in range(len(dp), a + 1):
		dp.append(dp[-1])
	for i in range(q):
		(x, y) = mp()
		x -= 1
		y -= b - 1
		if x < y:
			pr(dp[y] - dp[x])
		else:
			pr(0)
for _ in range(1):
	solve()


(n, m, q) = map(int, input().split())
s = input()
t = input()
x = 0
dp1 = []
while x < n:
	if s[x - m + 1:x + 1] == t:
		dp1.append(1)
	else:
		dp1.append(0)
	x += 1
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	acum = 0
	for j in range(i, n):
		if dp1[j] != 0 and j - m + 1 >= i:
			acum += dp1[j]
		dp[i][j] = acum
for i in range(q):
	(l, r) = map(int, input().split())
	print(dp[l - 1][r - 1])


import sys
(n, m, q) = map(int, input().split())
s = input()
t = input()
A = [None] * q
for i in range(q):
	A[i] = list(map(int, input().split()))
if m > n:
	for i in range(q):
		print(0)
	sys.exit()
score = [0 for i in range(n - m + 1)]
for i in range(n - m + 1):
	if t == s[i:i + m]:
		score[i] = 1
SUM = [0 for i in range(n - m + 1)]
SUM[0] = score[0]
for i in range(1, n - m + 1):
	SUM[i] = score[i] + SUM[i - 1]
SUM = [0] + SUM
for i in range(q):
	if A[i][1] - m + 1 <= A[i][0] - 1:
		print(0)
	else:
		print(SUM[A[i][1] - m + 1] - SUM[A[i][0] - 1])


f = lambda : list(map(int, input().split()))
ana1 = ''
(n, m, q) = f()
s = input()
t = input()
for _ in range(n - m + 1):
	if s[_:_ + m] == t:
		ana1 += '1'
	else:
		ana1 += '0'
for _ in range(q):
	(l, r) = f()
	if r - l + 1 >= m:
		print(ana1[l - 1:r - m + 1].count('1'))
	else:
		print(0)


M = 10000000007
b = 29
a = ord('a') - 1
(n, m, q) = map(int, input().split())
s = list(input())
t = list(input())
hs = [0] * (n + 1)
ps = [1] * (n + 1)
for i in range(n):
	hs[i + 1] = (hs[i] * b + ord(s[i]) - a) % M
	ps[i + 1] = ps[i] * b % M
h = 0
for i in range(m):
	h = (h * b + ord(t[i]) - a) % M
ans = [0] * (n + 1)
for i in range(n - m + 1):
	u = (hs[i + m] - hs[i] * ps[m]) % M
	if u == h:
		ans[i] = 1
for i in range(1, n):
	ans[i] += ans[i - 1]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	r -= m - 1
	if l > r:
		print(0)
	else:
		print(max(ans[max(r, 0)] - ans[l - 1], 0))


def KMPSearch(pat, txt):
	ans = []
	M = len(pat)
	N = len(txt)
	lps = [0] * M
	j = 0
	computeLPSArray(pat, M, lps)
	i = 0
	while i < N:
		if pat[j] == txt[i]:
			i += 1
			j += 1
		if j == M:
			ans.append(i - j)
			j = lps[j - 1]
		elif i < N and pat[j] != txt[i]:
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
	return ans

def computeLPSArray(pat, M, lps):
	len = 0
	lps[0]
	i = 1
	while i < M:
		if pat[i] == pat[len]:
			len += 1
			lps[i] = len
			i += 1
		elif len != 0:
			len = lps[len - 1]
		else:
			lps[i] = 0
			i += 1
(n, m, q) = map(int, input().split())
s = input().strip()
t = input().strip()
pos = KMPSearch(t, s)
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	ans = 0
	for a in pos:
		if a >= l and a + m <= r:
			ans += 1
	print(ans)


(n, m, q) = map(int, input().split())
s = input()
t = input()
if len(t) > len(s):
	for _ in range(q):
		print(0)
else:
	pos = s.find(t)
	cnt = [0]
	while pos != -1:
		while len(cnt) <= pos:
			cnt.append(cnt[-1])
		cnt.append(cnt[-1] + 1)
		pos = s.find(t, pos + 1)
	while len(cnt) < len(s) + 1:
		cnt.append(cnt[-1])
	for test in range(q):
		(left, right) = map(int, input().split())
		ans = cnt[right - len(t) + 1] - cnt[left - 1]
		if ans < 0 or right - left + 1 < len(t):
			ans = 0
		print(ans)


t = 1
for test in range(1, t + 1):
	(n, m, q) = map(int, input().split())
	s = input()
	t = input()
	indices = [0 for i in range(n)]
	for i in range(n):
		tmp = s.find(t, i)
		if tmp == -1:
			break
		else:
			indices[tmp] = 1
	pref = [0]
	for i in indices:
		pref.append(i + pref[-1])
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l + 1 < m:
			print(0)
			continue
		print(pref[r - m + 1] - pref[l - 1])


(n, m, q) = list(map(int, input().split()))
s = input()
t = input()

def check(i):
	if len(t) > len(s):
		return 0
	for k in range(i, i + len(t)):
		if s[k] != t[k - i]:
			return 0
	return 1
pref = [0]
for i in range(len(s) - len(t) + 1):
	pref.append(pref[-1] + check(i))
for i in range(len(s) - len(t) + 1, len(s)):
	pref.append(pref[-1])
for k in range(q):
	(l, r) = list(map(int, input().split()))
	r -= len(t) - 1
	if r < l:
		print(0)
		continue
	print(pref[r] - pref[l - 1])


(n, m, q) = list(map(int, input().split()))
a = input()
b = input()
c = [0]
for i in range(1, n + 1):
	c.append(c[i - 1] + (a[max(i - m, 0):i] == b))
for i in range(q):
	(l, r) = list(map(int, input().split()))
	if r - l >= m - 1:
		print(max(c[r] - c[l + m - 2], 0))
	else:
		print(0)


(n, m, q) = map(int, input().strip().split())
s = input()
t = input()
le = len(t)
l1 = [0 for i in range(n + 2)]
count = 0
for i in range(0, n - le + 1):
	if s[i:i + le] == t:
		l1[i + 1] = -1
		count = count + 1
l2 = [0 for i in range(n + 2)]
l2[1] = count
for i in range(2, n + 2):
	l2[i] = l2[i - 1] + l1[i - 1]
for i in range(q):
	(r1, r2) = map(int, input().strip().split())
	if r1 > r2 - le + 2:
		print(0)
		continue
	print(l2[r1] - l2[r2 - le + 2])


(n, m, q) = list(map(int, input().split()))
s = input()
t = input()
arr = [0] * n
for i in range(n - m + 1):
	if t == s[i:i + m]:
		arr[i] = 1
	if i:
		arr[i] += arr[i - 1]
for i in range(q):
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	L = l - 1
	R = r - m + 1
	if R < L:
		print(0)
		continue
	if L >= 0:
		print(arr[R] - arr[L])
	else:
		print(arr[R])


(n, m, q) = [int(s) for s in input().split()]
s = input()
t = input()
a = []
b = []
for i in range(n):
	b.append(0)
for i in range(n - m + 1):
	if s[i:i + m] == t:
		a.append(i)
for i in a:
	for j in range(i, n):
		b[j] += 1
l = []
r = []
for i in range(q):
	(x, y) = [int(item) for item in input().split()]
	l.append(x - 1)
	r.append(y - 1)
for i in range(q):
	if l[i] == 0:
		if r[i] - m + 1 >= l[i]:
			print(b[r[i] - m + 1])
		else:
			print(0)
	elif r[i] - m + 1 >= l[i]:
		print(b[r[i] - m + 1] - b[l[i] - 1])
	else:
		print(0)


from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
(n, m, q) = map(int, input().split())
pref = [0] * (n + 1)
s = input()
s1 = input()
for i in range(n):
	z = s[i:i + m]
	if z == s1:
		pref[i + 1] = 1
for i in range(q):
	(a, b) = map(int, input().split())
	b -= m
	b += 1
	if a <= b:
		print(sum(pref[a:b + 1]))
	else:
		print(0)


(n, m, q) = map(int, input().split())
s = input()
t = input()
st = [0] * n
en = [0] * n
for i in range(n):
	if s[i:i + m] == t:
		st[i] = 1
		en[i + m - 1] = 1
	if i > 0:
		st[i] += st[i - 1]
		en[i] += en[i - 1]
st.insert(0, 0)
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(max(0, en[r] - st[l]))


(n, m, q) = map(int, input().split())
s = input()
t = input()
x = []
for i in range(n):
	x.append([0] * n)
for i in range(n - m + 1):
	if s[i:i + m] == t:
		x[i][i + m - 1] = 1
for j in range(m, n):
	for i in range(n - j):
		x[i][i + j] = x[i + 1][i + j] + x[i][i + j - 1]
		if j > 1:
			x[i][i + j] -= x[i + 1][i + j - 1]
for i in range(q):
	(a, b) = map(int, input().split())
	print(x[a - 1][b - 1])


(n, m, q) = map(int, input().split())
goals = ''
(s, t) = (input(), input())
for _ in range(n - m + 1):
	if s[_:_ + m] == t:
		goals += '1'
	else:
		goals += '0'
for _ in range(q):
	arguments = input().split()
	l = int(arguments[0])
	r = int(arguments[1])
	if r - l + 1 >= m:
		print(goals[l - 1:r - m + 1].count('1'))
	else:
		print(0)


import sys
(n, m, t) = map(int, input().split())
s1 = list(input())
s2 = list(input())
d = {}
for i in range(n):
	inc = 0
	j = 0
	while i + inc < n and j < m and (s1[i + inc] == s2[j]):
		inc += 1
		j += 1
		if inc == m:
			d[i + m] = d.get(i + m, 0) + 1
s = 0
for i in range(0, 1001):
	d[i] = d.get(i, 0) + s
	s = d[i]
for _ in range(t):
	(x, y) = map(int, sys.stdin.readline().split())
	if y - x + 1 < m:
		print(0)
	else:
		ans = d[y] - d[x - 2 + m]
		print(ans)


(n, m, q) = [int(x) for x in input().split()]
s = input()
t = input()
cnt_lst = [0]
for i in range(len(s)):
	val = 1 if s.startswith(t, i) else 0
	cnt_lst.append(cnt_lst[-1] + val)
for i in range(q):
	(l, r) = [int(x) for x in input().split()]
	(x, y) = (l - 1, r - len(t) + 1)
	if x < y:
		print(cnt_lst[y] - cnt_lst[x])
	else:
		print(0)


import os, sys
from io import BytesIO, IOBase

def main():
	(n, m, q) = rints()
	(s, t, cum) = (rstr(), rstr(), [0] * (n + 1))
	for i in range(m - 1, n):
		(ix, cum[i]) = (m - 1, cum[i] + cum[i - 1])
		for j in range(i, i - m, -1):
			if s[j] != t[ix]:
				break
			ix -= 1
		else:
			cum[i] += 1
	for i in range(q):
		(l, r) = rints()
		if r - l + 1 >= m:
			print(cum[r - 1] - cum[l + m - 3])
		else:
			print(0)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 8192
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
main()


(n, m, q) = list(map(int, input().split()))
s = input()
t = input()
ans = []
counter = 0
dec = []
for i in range(0, n - m + 1):
	type(i)
	if s[i:i + m] == t:
		ans.append(1)
	else:
		ans.append(0)
for i in range(q):
	(start, stop) = list(map(int, input().split()))
	slice = ans[start - 1:stop - m + 1]
	if stop - start + 1 < m:
		dec.append(0)
		continue
	dec.append(slice.count(1))
print('\n'.join(map(str, dec)))


ch = input()
l = list(map(int, ch.split()))
m = l[0]
n = l[1]
p = l[2]
s = input()
t = input()
l1 = []
for i in range(p):
	ch = input()
	l1.append(ch)
res = 0
l2 = [0]
for i in range(len(t) - 1):
	l2.append(0)
for i in range(len(t) - 1, len(s)):
	if s[i - len(t) + 1:i + 1] == t:
		res += 1
	l2.append(res)
for i in range(p):
	ch = l1[i]
	l = list(map(int, ch.split()))
	r = l[0]
	k = l[1]
	if k - r + 1 >= len(t):
		print(l2[k] - l2[r - 2 + len(t)])
	else:
		print(0)


from sys import stdin
from math import *
line = stdin.readline().rstrip().split()
n = int(line[0])
m = int(line[1])
q = int(line[2])
s = stdin.readline().rstrip().split()[0]
t = stdin.readline().rstrip().split()[0]
bools = [0] * (n - m + 1 + 1)
accum = 0
for i in range(n - m, -1, -1):
	if s[i:i + m] == t:
		accum += 1
	bools[i] = accum
for i in range(q):
	numbers = list(map(int, stdin.readline().rstrip().split()))
	l = numbers[0] - 1
	r = numbers[1] - 1 - m + 1 + 1
	if r > l:
		print(bools[l] - bools[r])
	else:
		print(0)


(n, m, q) = map(int, input().split())
s = input()
t = input()
a = [0] * n
for i in range(n - m + 1):
	if s[i:i + m] == t:
		a[i] = 1
for i in range(q):
	k = 0
	(l, r) = map(int, input().split())
	for j in range(l - 1, r):
		if a[j] == 1 and j + m - 1 < r:
			k += 1
	print(k)


(n, m, q) = map(int, input().split())
s1 = input()
s2 = input()
ans = []
for i in range(0, len(s1) - len(s2) + 1):
	if s1[i:i + len(s2)] == s2:
		ans.append(True)
	else:
		ans.append(False)
for i in range(q):
	(l, r) = map(int, input().split())
	if r - l + 1 < len(s2):
		print(0)
		continue
	print(sum(ans[l - 1:r - len(s2) + 1]))


(a, b, c) = map(int, input().split())
str1 = input()
str2 = input()
string = ''
for i in range(a - b + 1):
	if str1[i:i + b] == str2:
		string += '1'
	else:
		string += '0'
for _ in range(c):
	(x, y) = map(int, input().split())
	if y - x + 1 >= b:
		print(string[x - 1:y - b + 1].count('1'))
	else:
		print(0)


(n, m, q) = map(int, input().split())
s = input()
t = input()
dictworks = [0] * n
for start in range(n - m + 1):
	works = True
	for i in range(m):
		if s[start + i] != t[i]:
			works = False
	dictworks[start] = works ^ 0
for tc in range(q):
	(l, r) = map(int, input().split())
	if r - m + 1 < l:
		print(0)
		continue
	print(sum(dictworks[l - 1:r - m + 1]))


import sys
(n, m, q) = map(int, sys.stdin.readline().split())
s = input()
t = input()
i = 0
j = 0
p = [0] * (n + 1)
res = [i for i in range(len(s)) if s.startswith(t, i)]
for i in range(len(res)):
	p[res[i] + 1] = 1
for i in range(2, n + 1):
	p[i] += p[i - 1]
for _ in range(q):
	(l, r) = map(int, sys.stdin.readline().split())
	r = r - m + 1
	ans = p[max(r, 0)] - p[l - 1]
	print(max(ans, 0))


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def _sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, val):
		i += 1
		while i <= self.size:
			self.bit[i] += val
			i += i & -i

	def get_sum(self, l, r):
		return self._sum(r) - self._sum(l)

def z_algo(s):
	res = [0] * len(s)
	res[0] = len(s)
	i = 1
	j = 0
	while i < len(s):
		while i + j < len(s) and s[j] == s[i + j]:
			j += 1
		res[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < len(s) and k + res[k] < j:
			res[i + k] = res[k]
			k += 1
		i += k
		j -= k
	return res
(n, m, q) = map(int, input().split())
s = input()[:-1]
t = input()[:-1]
query = [list(map(int, input().split())) for i in range(q)]
ss = t + s
tmp = z_algo(ss)
ans = [0] * n
for i in range(m, n + m):
	if tmp[i] >= len(t):
		ans[i - m] = 1
bit = BIT(n)
for i in range(n):
	bit.add(i, ans[i])
for (l, r) in query:
	l -= 1
	if l > r - len(t) + 1:
		print(0)
	else:
		print(bit.get_sum(l, r - len(t) + 1))


def substr(str, start, length):
	return str[start:length + start]

def main():
	(n, m, q) = map(int, input().split())
	s = input()
	t = input()
	a = [0] * n
	for i in range(n - m + 1):
		if substr(s, i, m) == t:
			a[i] = 1
	ans = []
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l + 1 < m:
			ans.append(0)
			continue
		ans.append(a[l - 1:r - m + 1].count(1))
	print('\n'.join(map(str, ans)))
main()


while True:
	try:

		def failur(p, m):
			failr = [0] * (m + 2)
			failr[0] = failr[1] = 0
			i = 2
			while i <= m:
				j = failr[i - 1]
				while True:
					if p[i - 1] == p[j]:
						failr[i] = j + 1
						break
					if j == 0:
						failr[i] = j
						break
					j = failr[j]
				i += 1
			return failr

		def matches(t, p, f):
			n = len(t)
			m = len(p)
			c = [0] * (n + 2)
			ti = pi = 0
			while True:
				if ti == n:
					break
				if t[ti] == p[pi]:
					pi += 1
					ti += 1
					if pi == m:
						pi = f[m]
						c[ti - m] += 1
				elif pi == 0:
					ti += 1
				else:
					pi = f[pi]
			return c

		def solution(n, m, q):
			qury = []
			test = input()
			patt = input()
			for i in range(q):
				(l, r) = map(int, input().split())
				l -= 1
				r -= 1
				qury.append([l, r])
			f = failur(patt, m)
			matc = matches(test, patt, f)
			for i in range(q):
				(a, b) = (qury[i][0], qury[i][1])
				rng = b - m + 1
				cunt = 0
				for j in range(a, rng + 1, 1):
					if matc[j] > 0:
						cunt += 1
				print(cunt)

		def read():
			(n, m, q) = map(int, input().split())
			solution(n, m, q)
		if __name__ == '__main__':
			read()
	except EOFError:
		break


(n, m, q) = map(int, input().split())
x = [0 for i in range(n + 1)]
b = input()
s = input()
for i in range(n - m + 1):
	f = True
	for j in range(i, i + m):
		if b[j] != s[j - i]:
			f = False
			break
	if f:
		x[i + m] = 1
for i in range(1, n + 1):
	x[i] = x[i] + x[i - 1]
x += [x[-1] for i in range(m)]
for _ in range(q):
	(l, r) = map(int, input().split())
	print(max(x[r] - x[l + m - 2], 0))


(n, m, q) = map(int, input().split())
s = input()
t = input()
if m == 0 or n == 0 or n < m:
	for i in range(q):
		print('0')
	exit()
occur = [0] * (n - m + 1)
for i in range(n - m + 1):
	if s[i:i + m] == t:
		occur[i] = occur[i - 1] + 1 if i > 0 else 1
	else:
		occur[i] = occur[i - 1] if i > 0 else 0
occur += [occur[-1]] * (m - 1)
occur = [0] + occur
for i in range(q):
	(l, r) = map(int, input().split())
	if r - l < m - 1:
		print(0)
	else:
		print(occur[r - m + 1 if r - m + 1 >= 0 else 0] - occur[l - 1])


(n, m, q) = map(int, input().split())
s = input()
t = input()
st = []
en = []

def check(i):
	if i > n - m:
		return False
	for j in range(i, i + m):
		if s[j] != t[j - i]:
			return False
	return True
for i in range(n):
	st.append(0)
	en.append(0)
for i in range(n):
	if check(i):
		st[i] = 1
		en[i + m - 1] = 1
	if i > 0:
		st[i] += st[i - 1]
		en[i] += en[i - 1]
st.insert(0, 0)
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(max(0, en[r] - st[l]))


(n, m, q) = map(int, input().split())
s = input()
t = input()
pr = [0] * (1000 + 7)
ok = [0] * (1000 + 7)
pr[0] = 0
for i in range(n - m + 1):
	fl = 1
	for j in range(m):
		if s[i + j] != t[j]:
			fl = 0
	ok[i] = fl
	pr[i + 1] = pr[i] + ok[i]
for i in range(max(0, n - m + 1), n):
	pr[i + 1] = pr[i]
while q > 0:
	(l, r) = map(int, input().split())
	l -= 1
	r -= m - 1
	if r >= l:
		print(pr[r] - pr[l])
	else:
		print(0)
	q -= 1


(n, m, q) = map(int, input().split())
s = input()
t = input()
arr = [0] * n
for i in range(n - m + 1):
	arr[i] = arr[i - 1]
	if s[i:i + m] == t:
		arr[i] += 1
for case in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	if r - m + 1 < 0:
		print(0)
	elif l == 0:
		print(arr[r - m + 1])
	elif r - m + 1 > l - 1:
		print(arr[r - m + 1] - arr[l - 1])
	else:
		print(0)


import sys
from array import array

def readline():
	return sys.stdin.buffer.readline().decode('utf-8')
(n, m, q) = map(int, readline().split())
(s, t) = ('*' + readline().rstrip(), readline().rstrip())
dp_r = [0] * (n + 1)
dp_l = [0] * (n + 1)
for i in range(m, n + 1):
	if s[i - m + 1:i + 1] == t:
		dp_r[i] = 1
		dp_l[i - m + 1] = 1
for i in range(n):
	dp_r[i + 1] += dp_r[i]
	dp_l[i + 1] += dp_l[i]
ans = [0] * q
for i in range(q):
	(l, r) = map(int, readline().split())
	if r - l + 1 >= m:
		ans[i] = dp_r[r] - dp_l[l - 1]
sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))


def mi():
	return map(int, input().split())
(n, m, q) = mi()
s = list(input())
t = list(input())
pre1 = [0] * n
pre2 = [0] * n
if n >= m:
	for i in range(n - m + 1):
		if s[i:i + m] == t:
			pre1[i + m - 1] = 1
			pre2[i] = 1
	for i in range(1, n):
		pre1[i] += pre1[i - 1]
		pre2[i] += pre2[i - 1]
pre1.insert(0, 0)
pre2.insert(0, 0)
while q:
	q -= 1
	(l, r) = mi()
	(s1, s2) = (0, 0)
	if m > n:
		print(0)
		continue
	if r < m or r - l + 1 < m or n - l + 1 < m:
		print(0)
		continue
	s1 = pre1[r] - pre1[l - 1 + m - 1]
	s2 = pre2[r - m + 1] - pre2[l - 1]
	if s1 > 0 and s2 > 0:
		print(min(s1, s2))
	else:
		print(0)


def main():
	(n, m, q) = map(int, input().split())
	s = input()
	t = input()
	matrix = [[0 for i in range(n)] for i in range(n)]
	for l in range(n):
		for r in range(l + m - 1, n):
			if s[r - m + 1:r + 1] == t:
				matrix[l][r] = matrix[l][r - 1] + 1
			else:
				matrix[l][r] = matrix[l][r - 1]
	for i in range(q):
		(l, r) = map(int, input().split())
		print(matrix[l - 1][r - 1])
main()


(n, m, q) = map(int, input().split())
s = input()
t = input()
k = [0] * (n + 1)
for i in range(1, n + 1):
	k[i] = k[i - 1]
	if s[i - 1:i + m - 1] == t:
		k[i] += 1
for i in range(q):
	(l, r) = map(int, input().split())
	print(k[max(l - 1, r - m + 1)] - k[l - 1])


(n, m, q) = map(int, input().split())
a = input()
b = input()
wynik = ''
for i in range(0, n - m + 1):
	if a[i:i + m] == b:
		wynik += '1'
	else:
		wynik += '0'
for i in range(q):
	(x, y) = map(int, input().split())
	if y - x + 1 >= m:
		print(wynik[x - 1:y - m + 1].count('1'))
	else:
		print(0)


(n, m, q) = map(int, input().split())
a = input()
b = input()
flags = [0] * 1007
pr = [0] * 1007
for i in range(n - m + 1):
	f = 1
	for j in range(m):
		if a[i + j] != b[j]:
			f = 0
	flags[i] = f
	pr[i + 1] = pr[i] + flags[i]
for i in range(max(0, n - m + 1), n):
	pr[i + 1] = pr[i]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= m - 1
	if r >= l:
		print(pr[r] - pr[l])
	else:
		print(0)


(n, m, q) = list(map(int, input().split()))
s = input()
t = input()
l = []
r = []
for i in range(n - m + 1):
	if s[i:i + m] == t:
		l.append(i)
		r.append(i + m - 1)
for i in range(q):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	ans = 0
	for j in range(len(l)):
		if x <= l[j] and y >= r[j]:
			ans += 1
	print(ans)


(n, m, q) = list(map(int, input().split()))
s = str(input())
t = str(input())
arrx = []
i = 0
count = 0
while i < n:
	if s[i] == t[0]:
		j = 0
		while j + i < n and j < m and (s[j + i] == t[j]):
			j += 1
		if j == len(t):
			count += 1
	arrx.append(count)
	i += 1
for i in range(q):
	(x, y) = list(map(int, input().split()))
	if y - x < m - 1:
		print(0)
	elif x == 1:
		print(arrx[y - m])
	else:
		print(arrx[y - m] - arrx[x - 2])


(n, m, q) = map(int, input().split())
s = input()
t = input()
dp = [[0 for i in range(n)] for i in range(n)]
for left in range(n):
	for right in range(left + m - 1, n):
		if s[right - m + 1:right + 1] == t:
			dp[left][right] = dp[left][right - 1] + 1
		else:
			dp[left][right] = dp[left][right - 1]
for i in range(q):
	(left, right) = map(int, input().split())
	print(dp[left - 1][right - 1])


(n, m, q) = map(int, input().split())
s = input()
t = input()
w = s
ind = w.find(t)
a = []
st = [0]
en = [0] * (m - 1)
count = 0
pred = 0
while ind != -1:
	if len(a) > 0:
		el = a[-1]
	else:
		el = -1
	a.append(el + ind + 1)
	st += [count] * (el + ind + 1 - pred)
	en += [count] * (el + ind + 1 - pred)
	count += 1
	pred = el + ind + 1
	w = w[ind + 1:]
	ind = w.find(t)
st += [count] * (n - pred)
en += [count] * (n - pred - m + 1)
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	if en[r] - st[l] >= 0:
		print(en[r] - st[l])
	else:
		print(0)


def pref_func(s):
	n = len(s)
	f = list()
	f.append(0)
	for i in range(1, n):
		j = f[i - 1]
		while j > 0 and s[i] != s[j]:
			j = f[j - 1]
		if s[i] == s[j]:
			j += 1
		f.append(j)
	return f
(n, m, q) = list(map(int, input().split(' ')))
s = input()
t = input()
f = pref_func(t + '$' + s)[m + 1:]
y = 0
suf = list()
for i in range(n - 1, -1, -1):
	suf.append(y)
	if f[i] == m:
		y += 1
suf.reverse()
for i in range(n):
	if f[i] == m:
		f[i] = 0
		f[i - m + 1] = 1
	else:
		f[i] = 0
pre = list()
y = 0
for i in range(n):
	pre.append(y)
	if f[i] == 1:
		y += 1
mmm = f.count(1)
for i in range(q):
	(l, r) = list(map(int, input().split(' ')))
	print(max(mmm - pre[l - 1] - suf[r - 1], 0))


def read():
	return int(input())

def readlist():
	return list(map(int, input().split()))

def readmap():
	return map(int, input().split())
(n, m, q) = readmap()
S = input()
T = input()
L = []
R = []
for _ in range(q):
	(l, r) = readmap()
	L.append(l)
	R.append(r)
left = [0] * n
right = [0] * n
for i in range(n - m + 1):
	if S[i:i + m] == T:
		for j in range(i + 1, n):
			left[j] += 1
		for j in range(i + m - 1, n):
			right[j] += 1
for i in range(q):
	(l, r) = (L[i], R[i])
	print(max(0, right[r - 1] - left[l - 1]))


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	(n, m, q) = map(int, input().split())
	string = input().rstrip()
	substring = input().rstrip()
	sequence = [0]
	freq = 0
	for i in range(n):
		if string[i:i + m] == substring:
			freq += 1
		sequence.append(freq)
	for i in range(q):
		(l, r) = map(int, input().split())
		print(sequence[max(l - 1, r - m + 1)] - sequence[l - 1])
for _ in range(1):
	solve()


import sys
line1 = sys.stdin.readline().strip('\n')
line2 = sys.stdin.readline().strip('\n')
line3 = sys.stdin.readline().strip('\n')
(a, b, n) = list(map(int, line1.split()))
sum = [0] * len(line3)
for i in range(len(line2)):
	if line2[i:i + len(line3)] == line3:
		sum.append(1)
	else:
		sum.append(0)
for i in range(len(sum)):
	if i > 0:
		sum[i] = sum[i - 1] + sum[i]
for i in range(n):
	line2 = sys.stdin.readline().strip('\n')
	(a, b) = list(map(int, line2.split()))
	if b - a + 1 < len(line3):
		print(0)
	else:
		print(sum[b] - sum[a + len(line3) - 2])


(n, m, q) = map(int, input().split())
a = input()
b = input()
c = [0]
d = 0
for i in range(m - 1, n):
	if a[i - m + 1:i + 1] == b:
		d += 1
	c.append(d)
for i in range(q):
	(x, y) = map(int, input().split())
	if y - x + 1 < m:
		print(0)
	else:
		print(max(c[y - m + 1] - c[x - 1], 0))


(n, m, q) = (int(x) for x in input().split())
s = input()
t = input()
X = set()
for i in range(len(s) - len(t) + 1):
	if s[i:i + len(t)] == t:
		X.add(i)
Y = [0]
for i in range(len(s)):
	tm = Y[-1]
	if i in X:
		tm += 1
	Y.append(tm)
for _ in range(q):
	(l, r) = (int(x) for x in input().split())
	print(0 if r - len(t) + 1 < l - 1 else Y[r - len(t) + 1] - Y[l - 1])


(n, m, q) = list(map(int, input().split()))
s = str(input())
t = str(input())

def is_in(index):
	if index + m > n:
		return False
	for j in range(m):
		if not t[j] == s[index + j]:
			return False
	return True
precalc_ar_2 = [0 for i in range(n + 1)]
in_was = [False for i in range(n)]
for i in range(n):
	if is_in(i):
		in_was[i] = True
val = 0
for i in range(1, n + 1):
	if in_was[i - 1]:
		val += 1
	precalc_ar_2[i] = val
for i in range(q):
	(l, r) = list(map(int, input().split()))
	if r - m + 1 < 0 or r - m + 1 < l - 1:
		print(0)
	else:
		print(precalc_ar_2[r - m + 1] - precalc_ar_2[l - 1])


from collections import defaultdict
import sys, heapq, bisect, math, itertools, string, queue, datetime
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)
AtoZ = [chr(i) for i in range(65, 65 + 26)]
atoz = [chr(i) for i in range(97, 97 + 26)]

def inpl():
	return list(map(int, input().split()))

def inpl_str():
	return list(input().split())
(N, M, q) = inpl()
S = input()
T = input()
azu = [0] * (N - M + 1)
qq = []
for i in range(q):
	qq.append(inpl())
if M > N:
	for i in range(q):
		print(0)
	return
for i in range(0, N - M + 1):
	if S[i:i + M] == T:
		azu[i] = 1
SUM = 0
nyan = [0]
for az in azu:
	SUM += az
	nyan.append(SUM)
for (l, r) in qq:
	l -= 1
	if r - l < M:
		print(0)
	else:
		print(nyan[r - M + 1] - nyan[l])


(n, m, q) = list(map(int, input().split()))
s = input()
t = input()
tt = [0] * 1111
for i in range(n - m + 1):
	j = 0
	while j < m and s[i + j] == t[j]:
		j += 1
	if j >= m:
		tt[i + 1] = 1
for i in range(1, n + 1):
	tt[i] += tt[i - 1]
for i in range(q):
	(a, b) = list(map(int, input().split()))
	if b - a + 1 < m:
		print(0)
		continue
	print(tt[b - m + 1] - tt[a - 1])


import sys
FILE_IO = False
if FILE_IO:
	input_stream = open('input_test.txt')
	sys.stdout = open('current_output.txt', 'w')
else:
	input_stream = sys.stdin
(n, m, q) = map(int, input_stream.readline().split())
s = input_stream.readline().split()[0]
t = input_stream.readline().split()[0]
dp = [[0] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
	for j in range(n + 1):
		if i == 0 or j == 0:
			dp[i][j] = 0
		elif t[i - 1] == s[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = 0
sum_list = []
current_sum = 0
for elem in dp[m]:
	if elem == m:
		current_sum += 1
	sum_list.append(current_sum)
for _ in range(q):
	(start, end) = map(int, input_stream.readline().split())
	if start + m - 1 > end:
		print(0)
		continue
	print(sum_list[end] - sum_list[start + m - 2])


(n, m, q) = input().split(' ')
n = int(n)
m = int(m)
q = int(q)
s = input()
t = input()
length = len(t)
su = [0]
now = 0
for i in range(len(s) - length + 1):
	if s[i:i + length] == t:
		now += 1
	su.append(now)
for i in range(q):
	(l, r) = input().split(' ')
	l = int(l)
	r = int(r) - length + 1
	if r >= l:
		print(str(su[r] - su[l - 1]))
	else:
		print(0)


(N, M, Q) = [int(x) for x in input().split()]
S = input()
T = input()
A = []
pref = []
for i in range(N):
	A.append(0)
	pref.append(0)
for i in range(N):
	if S[i:i + M] == T:
		A[i] = 1
	if i > 0:
		pref[i] = pref[i - 1] + A[i]
	else:
		pref[i] = A[i]
for i in range(Q):
	(l, r) = [int(x) for x in input().split()]
	l -= 1
	r -= 1
	if r - l + 1 >= M:
		if r - M + 1 >= 0:
			if l - 1 >= 0:
				print(pref[r - M + 1] - pref[l - 1])
			else:
				print(pref[r - M + 1])
		else:
			print(0)
	else:
		print(0)


(n, m, q) = map(int, input().split())
s = input()
t = input()
a = [0] * (n + 1)
for i in range(n - m + 1):
	if s[i:i + m] == t:
		a[i + 1] += 1
S = [0] * (n + 1)
for i in range(1, n + 1):
	S[i] += S[i - 1] + a[i]
for i in range(q):
	(l, r) = map(int, input().split())
	if r + 1 - l >= m:
		print(S[r - m + 1] - S[l - 1])
	else:
		print(0)


import sys
sys.setrecursionlimit(2000)
from collections import Counter
from functools import reduce
(n, m, q) = [int(val) for val in sys.stdin.readline().split()]
s = input()
t = input()
count = [int(s[i:i + m] == t) for i in range(n)]
for query in range(q):
	(l, r) = [int(val) - 1 for val in sys.stdin.readline().split()]
	print(sum(count[l:max(l, r + 2 - m)]))


from itertools import accumulate
(N, M, Q) = [int(x) for x in input().split()]
S = input()
T = input()
(L, R) = ([0] * Q, [0] * Q)
for i in range(Q):
	(L[i], R[i]) = [int(x) for x in input().split()]
is_substr = [0] * N
for i in range(N):
	if S[i:i + M] == T:
		is_substr[i] = 1
prefixes = [0] + list(accumulate(is_substr))
output = [0] * Q
for i in range(Q):
	if R[i] - L[i] + 1 < M:
		continue
	output[i] = prefixes[R[i] - M + 1] - prefixes[L[i] - 1]
print('\n'.join(map(str, output)))


def prefix_func(s):
	(slen, k) = (len(s), 0)
	p = [0] * slen
	p[0] = 0
	for i in range(1, slen):
		while k > 0 and s[k] != s[i]:
			k = p[k - 1]
		if s[k] == s[i]:
			k += 1
		p[i] = k
	return p

def kmp(s, p):
	(q, slen, plen) = (0, len(s), len(p))
	res = []
	pi = prefix_func(p)
	for i in range(slen):
		while q > 0 and p[q] != s[i]:
			q = pi[q - 1]
		if p[q] == s[i]:
			q += 1
		if q == plen:
			res.append(i - plen + 1)
			q = pi[q - 1]
	return res
(n, m, q) = map(int, input().split())
s = input()
t = input()
matches = kmp(s, t)
match_count = [0] * (len(s) + 1)
for m in matches:
	match_count[m] = 1
count = 0
for i in range(len(s) - 1, 0, -1):
	match_count[i - 1] += match_count[i]
for i in range(q):
	(l, r) = map(int, input().split())
	r += 1
	ans = 0
	if r - l >= len(t):
		ans = match_count[l - 1] - match_count[r - len(t)]
	print(ans)


(n, m, q) = map(int, input().split())
s = input()
t = input()
f = ''
for i in range(n - m + 1):
	if s[i:i + m] == t:
		f += '1'
	else:
		f += '0'
ans = []
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	ans.append(f[l:max(r - m + 1, 0)].count('1'))
for i in ans:
	print(i)


(n, m, q) = map(int, input().split())
s = input()
t = input()
res = ''
if n >= m:
	for i in range(n):
		if s[i:i + m] == t:
			res += '1'
		else:
			res += '0'
for i in range(q):
	(c0, c1) = map(int, input().split())
	if m > n or c1 - c0 + 1 < m:
		print(0)
	else:
		print(res[c0 - 1:c1 - m + 1].count('1'))


(n, m, k) = map(int, input().split())
s = input()
t = input()
ans = [0] * n
for i in range(n - m + 1):
	if s[i:i + m] == t:
		ans[i] = 1
for tc in range(k):
	(x, y) = map(int, input().split())
	if y - x + 1 < m:
		print(0)
	else:
		print(sum(ans[x - 1:y - m + 1]))


from sys import stdout
print = stdout.write
(n, m, q) = map(int, input().split())
s = str(input())
t = str(input())
ans = []
i = j = 0
while True:
	x = s.find(t, i)
	if x != -1:
		for _ in range(x - i + 1):
			ans.append(j)
		j += 1
		i = x + 1
	else:
		ans += [j] * (n - i + 2)
		break
for _ in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= m - 1
	print(str(ans[r] - ans[l]) if r > l else str(0))
	print('\n')


(n, m, q) = map(int, input().split())
s = input()
t = input()
flag = [0] * 1007
prefix = [0] * 1007
for i in range(n - m + 1):
	f = 1
	for j in range(m):
		if s[i + j] != t[j]:
			f = 0
	flag[i] = f
	prefix[i + 1] = prefix[i] + flag[i]
for i in range(max(0, n - m + 1), n):
	prefix[i + 1] = prefix[i]
for _ in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= m - 1
	print(prefix[r] - prefix[l]) if r >= l else print(0)


import sys
import itertools
input = sys.stdin.readline

def main():
	(N, M, Q) = [int(x) for x in input().split()]
	S = input().strip()
	T = input().strip()
	LR = [[int(x) for x in input().split()] for _ in range(Q)]
	ans = [0] * (N + 1)
	for i in range(N):
		if S[i:i + M] == T:
			ans[i + M] = 1
	ansaccu = list(itertools.accumulate(ans))
	for (l, r) in LR:
		if r - l + 1 < M:
			print(0)
		else:
			print(ansaccu[r] - ansaccu[max(0, l + M - 2)])
main()


try:
	while True:
		(n, m, q) = list(map(int, input().split()))
		str1 = input()
		str2 = input()
		cnt = [0] * (n + 1)
		for l in range(n):
			if str1[l:min(l + m, n)] == str2:
				cnt[l + 1] = cnt[l] + 1
			else:
				cnt[l + 1] = cnt[l]
		for i in range(q):
			(l, r) = list(map(int, input().split()))
			print(cnt[max(l - 1, r - m + 1)] - cnt[l - 1])
except Exception as e:
	pass


def main():
	(n, m, q) = map(int, input().split())
	(s, t) = (input(), input())
	(start, ps) = ([0] * n, [0] * (n + 1))
	for i in range(n):
		(curr, left) = (0, i)
		while left < n and s[left] == t[curr]:
			curr += 1
			left += 1
			if curr == m:
				start[i] = 1
				break
	for i in range(n):
		ps[i + 1] = ps[i] + start[i]
	for i in range(q):
		(l, r) = map(int, input().split())
		print(0) if r - l + 1 < m else print(ps[r - m + 1] - ps[l - 1])
main()


(n, m, q) = map(int, input().split())
s = input()
t = input()
a = []
b = []
c = [0] * n
for i in range(n):
	if s[i:i + m] == t:
		b.append([i, i + m])
x = 0
y = 0
for i in range(n):
	c[i] = y
	if x < len(b) and i == b[x][0]:
		x += 1
		y += 1
x = 0
y = 0
d = [0] * n
for i in range(n):
	if x < len(b) and i + 1 == b[x][1]:
		x += 1
		y += 1
	d[i] = y
for i in range(q):
	x = list(map(int, input().split()))
	y = d[x[1] - 1] - c[x[0] - 1]
	if y < 0:
		y = 0
	print(y)


(n, m, q) = map(int, input().split())
s = input()
t = input()
ht = hash(t)
hss = [hash(s[i:i + m]) for i in range(n - m + 1)]
lhss = n - m + 1
for i in range(q):
	(l, r) = map(int, input().split())
	c = 0
	for j in range(l - 1, r):
		if j + m > r:
			continue
		if j < lhss and hss[j] == ht:
			c += 1
	print(c)


def z_algorithm(s):
	n = len(s)
	Z = [0] * n
	Z[0] = n
	i = 1
	j = 0
	while i < n:
		while i + j < n and s[j] == s[i + j]:
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < n and k + Z[k] < j:
			Z[i + k] = Z[k]
			k += 1
		i += k
		j -= k
	return Z

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (self.n + 1)

	def init(self, init_val):
		for (i, v) in enumerate(init_val):
			self.add(i, v)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def sum(self, i, j):
		return self._sum(j) - self._sum(i)

	def _sum(self, i):
		res = 0
		while i > 0:
			res += self.bit[i]
			i -= i & -i
		return res

	def lower_bound(self, x):
		s = 0
		pos = 0
		depth = self.n.bit_length()
		v = 1 << depth
		for i in range(depth, -1, -1):
			k = pos + v
			if k <= self.n and s + self.bit[k] < x:
				s += self.bit[k]
				pos += v
			v >>= 1
		return pos

	def __str__(self):
		arr = [self.sum(i, i + 1) for i in range(self.n)]
		return str(arr)
import sys
import io, os
input = sys.stdin.readline
(n, m, q) = map(int, input().split())
s = str(input().rstrip())
t = str(input().rstrip())
S = t + '#' + s
Z = z_algorithm(S)
Z = Z[m + 1:]
LR = []
for i in range(q):
	(l, r) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	LR.append((l, r, 1, i))
for i in range(n):
	if Z[i] == m:
		LR.append((i, i + m - 1, 0, 0))
LR.sort(key=lambda x: (x[1], x[2]))
bit = BIT(10 ** 3 + 50)
ans = [0] * q
for (l, r, t, i) in LR:
	if t == 0:
		bit.add(l, 1)
	else:
		ans[i] = bit.sum(l, r + 1)
print(*ans, sep='\n')


import bisect

def occurances(s, t):
	locations = []
	for i in range(len(s) - len(t) + 1):
		if t == s[i:i + len(t)]:
			locations.append(i)
	return locations
(n, m, num_queries) = list(map(int, input().split(' ')))
s = input()
t = input()
locations = occurances(s, t)
for i in range(num_queries):
	(start, end) = list(map(int, input().split(' ')))
	start -= 1
	end -= 1
	if end - start + 1 < len(t):
		print(0)
	else:
		start_idx = bisect.bisect_left(locations, start)
		end_idx = bisect.bisect(locations, end - len(t) + 1)
		print(end_idx - start_idx)


(n, m, q) = map(int, input().split())
s = input()
t = input()
a = [0] * n
for i in range(n - m + 1):
	if s[i:i + m] == t:
		a[i] = 1
for k in range(q):
	(l, r) = map(int, input().split())
	l = l - 1
	r = r - m
	res = sum(a[l:r + 1]) if l <= r else 0
	print(res)


tmp = input().split()
n = int(tmp[0])
m = int(tmp[1])
q = int(tmp[2])
arr1 = []
arr2 = []
tmp = input()
for i in tmp:
	arr1.append(i)
tmp = input()
for i in tmp:
	arr2.append(i)
hash = [0 for i in range(n + 10)]
for i in range(n - m + 1):
	if arr2 == arr1[i:i + m:1]:
		hash[i + 1] = 1
for i in range(1, n + 2, 1):
	hash[i] += hash[i - 1]
for i in range(q):
	tmp = input().split()
	l = int(tmp[0])
	r = int(tmp[1])
	if r - l + 1 < m or m > n:
		ans = 0
	else:
		ans = hash[r - m + 1] - hash[l - 1]
	print(ans)


from sys import stdin, stdout
(a, b, c) = map(int, stdin.readline().split())
z = stdin.readline()
z1 = stdin.readline()
p = []
k = [list(map(int, stdin.readline().split())) for _ in ' ' * c]
for i in range(a - b + 1):
	for j in range(b):
		if z[i + j] != z1[j]:
			break
	else:
		p += [[i + 1, i + b]]
o = [0] * c
for i in p:
	for j in range(c):
		if k[j][0] <= i[0] and i[1] <= k[j][1]:
			o[j] += 1
stdout.write(' '.join(map(str, o)))


Input = lambda : map(int, input().split())
(n, m, q) = Input()
s = input()
t = input()
pre = [0 for i in range(n + 5)]
for i in range(0, n - m + 1):
	if s[i:i + m] == t:
		pre[i + 1] = 1
for i in range(1, n + 3):
	pre[i] += pre[i - 1]
for i in range(q):
	(l, r) = Input()
	if r - l + 1 < m:
		print(0)
		continue
	print(pre[r - m + 1] - pre[l - 1])


from sys import stdin, stdout
from collections import Counter
import math
I = lambda : map(int, stdin.readline().split())
I1 = lambda : stdin.readline()
(n, m, q) = I()
(s, t) = (I1().strip(), I1().strip())
a = [0] * (n + 1)
for i in range(n):
	if i + m <= n and s[i:i + m] == t:
		a[i + 1] += a[i] + 1
	else:
		a[i + 1] += a[i]
for i in range(q):
	(l, r) = I()
	if r - l + 1 < m:
		print(0)
	else:
		print(a[r - m + 1] - a[l - 1])


def binary_search(array, target):
	lower = 0
	upper = len(array)
	while lower < upper:
		x = lower + (upper - lower) // 2
		val = array[x]
		if target == val:
			return x
		elif target > val:
			if lower == x:
				break
			lower = x
		elif target < val:
			upper = x
(n, m, q) = [int(i) for i in input().split()]
s = str(input())
t = str(input())
z = [[int(i) for i in input().split()] for j in range(q)]
a = []
for i in range(n - m + 1):
	a += [i + 1]
	if s[i:i + m] == t:
		a.append(i + 1)
a += [i + 1 for i in range(n - m + 1, n)]
for i in range(q):
	l = z[i][0]
	r = z[i][1] - m + 1
	if l > r:
		print(0)
		continue
	c = binary_search(a, l)
	d = binary_search(a, r)
	try:
		if a[d + 1] == a[d]:
			d += 1
	except:
		pass
	try:
		if a[c - 1] == a[c] and c >= 1:
			c -= 1
	except:
		pass
	print(d - c - r + l)


import sys
import io
stream_enable = 0
inpstream = '\n15 2 3\nabacabadabacaba\nba\n1 15\n3 4\n2 14\n'
if stream_enable:
	sys.stdin = io.StringIO(inpstream)
	input()

def inpmap():
	return list(map(int, input().split()))
(n, m, q) = inpmap()
a = input()
b = input()
s = [0] * n
s[0] = int(a.startswith(b))
for i in range(1, n):
	s[i] = s[i - 1] + int(a[i:i + m] == b)
for i in range(q):
	(x, y) = inpmap()
	r = (s[y - m] if y - m >= 0 else 0) - (s[x - 2] if x - 2 >= 0 else 0)
	print(max(r, 0))


def main():
	[n, m, q] = list(map(int, input().split(' ')))
	s = input()
	t = input()
	queries = []
	for _ in range(q):
		queries.append(list(map(int, input().split(' '))))
	if len(s) < len(t):
		for _ in range(q):
			print(0)
	else:
		ref = [0]
		for i in range(len(s) - len(t) + 1):
			j = i
			if s[j:j + len(t)] == t:
				ref.append(ref[-1] + 1)
			else:
				ref.append(ref[-1])
		for x in queries:
			if x[1] - len(t) + 1 < x[0] - 1:
				print(0)
			else:
				print(ref[x[1] - len(t) + 1] - ref[x[0] - 1])
main()


(n, m, k) = map(int, input().split())
s = input()
st = input()
ar = [0 for i in range(n)]
pr = [0 for i in range(n + 1)]
for i in range(n - m + 1):
	found = 1
	for j in range(m):
		if s[i + j] != st[j]:
			found = 0
			break
	ar[i] = found
	pr[i + 1] = pr[i] + ar[i]
for i in range(max(0, n - m + 1), n):
	pr[i + 1] = pr[i]
for i in range(k):
	(l, r) = map(int, input().split())
	if r - l + 1 < m:
		print(0)
	else:
		print(pr[r - m + 1] - pr[l - 1])


import bisect
first = list(map(int, input().split()))
a = input()
b = input()
(n, m, q) = (first[0], first[1], first[2])
starts = []
for i in range(n - m + 1):
	if a[i:i + m] == b:
		starts.append(i + 1)
for _ in range(q):
	endpoints = list(map(int, input().split()))
	print(max(0, bisect.bisect_left(starts, endpoints[1] - m + 2) - bisect.bisect_left(starts, endpoints[0])))


(n, m, q) = map(int, input().split())
s = input()
t = input()
arr = []
for i in range(n - m + 1):
	if s[i:i + m] == t:
		arr.append(i)
for i in range(q):
	(l, r) = map(int, input().split())
	k = 0
	for j in range(len(arr)):
		if arr[j] >= l - 1 and arr[j] + m - 1 <= r - 1:
			k = k + 1
	print(k)


(n, m, q) = map(int, input().split())
s = input()
t = input()
start = {}
for i in range(1, n + 1):
	start[i] = False
for i in range(n - m + 1):
	if s[i:i + m] == t:
		start[i + 1] = True
d = {}
for i in range(1, n + 1):
	for j in range(i, n + 1):
		d[i, j] = 0
for i in range(1, n + 1):
	cnt = 0
	for j in range(i, n - m + 2):
		if start[j]:
			cnt += 1
		d[i, j + m - 1] += cnt
for i in range(q):
	(l, r) = map(int, input().split())
	print(d[l, r])


(n, m, q) = map(int, input().split())
s = input()
t = input()
len_t = len(t)
len_s = len(s)
ans = ''
for i in range(len_s):
	if s[i:len_t + i] == t:
		ans += '1'
	else:
		ans += '0'
for i in range(q):
	(l, r) = map(int, input().split())
	r -= len_t
	l -= 1
	r += 1
	r = max(0, r)
	l = max(0, l)
	if r > l:
		print(ans[l:r].count('1'))
	else:
		print(0)


(n, m, q) = map(int, input().split())
s = input()
t = input()
gas = ['LOL']
otv = []
c = m - 2
for i in range(n):
	if s[i:i + m] == t:
		gas.append(1)
	else:
		gas.append(0)
for i in range(q):
	(l, r) = map(int, input().split())
	if r - m >= 0:
		otv.append(str(sum(gas[l:r - c])))
	else:
		otv.append('0')
print('\n'.join(otv))


import bisect
f = lambda : map(int, input().split())
(n, m, q) = f()
(s, t) = (input(), input())
(x, st) = ([], [])
c1 = 0
for i in range(n):
	if ''.join((c for c in s[i:i + m])) == t:
		x.append(i + 1)
		c1 += 1
for i in range(q):
	cnt = 0
	(l, r) = f()
	if x != [] and r - l + 1 >= m:
		r = r - m + 1
		left = bisect.bisect_left(x, l)
		right = bisect.bisect_left(x, r)
		if right >= c1:
			right -= 1
		if x[right] > r:
			right -= 1
		cnt = right - left + 1
	st.append(str(cnt))
print('\n'.join(st))


(n, m, q) = map(int, input().split())
a = input()
b = input()
ans = [0 for i in range(n)]
for i in range(n - m + 1):
	if a[i] == b[0]:
		t = 0
		for j in range(1, m):
			if a[j + i] != b[j]:
				t = 1
				break
		if t == 0:
			ans[i] += 1
sub = [0]
for i in ans:
	sub.append(sub[-1] + i)
for _ in range(q):
	(l, r) = map(int, input().split())
	if r - l + 1 < m:
		print(0)
	else:
		print(sub[r - m + 1] - sub[l - 1])


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from heapq import heappush, heappop, heapify
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
(n, m, q) = zzz()
arr = getStr()
target = getStr()
ans = [0] * (max(n, m) + 2)
for i in range(n):
	if arr[i:i + m] == target:
		ans[i + 1] += 1
	ans[i + 1] += ans[i]
for i in range(q):
	(l, r) = zzz()
	print(max(0, ans[max(0, r - m + 1)] - ans[l - 1]))


string = ''
array = []
(n, m, q) = map(int, input().split())
s = input()
t = input()
for i in range(0, n - m + 1):
	if s[i:i + m] == t:
		string += '1'
	else:
		string += '0'
for i in range(0, q):
	(a, b) = map(int, input().split())
	if b - a + 1 >= m:
		array.append(string[a - 1:b - m + 1].count('1'))
	else:
		array.append(0)
for i in range(0, q):
	print(array[i], end='\n')


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, **kwargs, file=sys.stderr)
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N, M, Q) = getIntList()
s1 = input()
s2 = input()
tot = 0
zt = [0]
for i in range(N):
	if s1[i:i + M] == s2:
		tot += 1
	zt.append(tot)
dprint(zt)
for i in range(Q):
	(a, b) = getIntList()
	b0 = b - M + 1
	if b0 < a:
		print(0)
	else:
		print(zt[b0] - zt[a - 1])


import os, sys
from io import BytesIO, IOBase

def main():
	(n, m, q) = rints()
	(s, t, cum) = (rstr(), rstr(), [])
	for i in range(n - m + 1):
		if s[i:i + m] == t:
			cum.append((i + 1, i + m))
	for i in range(q):
		(l, r) = rints()
		ans = 0
		for (l1, r1) in cum:
			if l <= l1 and r >= r1:
				ans += 1
		print(ans)
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
main()


a = []
b = []
for i in range(3):
	a.append(input())
for n in range(int(a[0].split(' ')[2])):
	b.append(input())
c = 0
lent = 0
d = []
sum = []
sum.append(0)
while lent <= int(a[0].split(' ')[0]) - int(a[0].split(' ')[1]):
	if a[1][lent:int(a[0].split(' ')[1]) + lent] == a[2]:
		d.append(1)
	else:
		d.append(0)
	sum.append(sum[lent] + d[lent])
	lent = lent + 1
for z in range(len(b)):
	l = int(b[z].split(' ')[0])
	r = int(b[z].split(' ')[1]) - int(a[0].split(' ')[1]) + 1
	if int(b[z].split(' ')[1]) - l >= int(a[0].split(' ')[1]) - 1:
		print(sum[r] - sum[l - 1])
	else:
		print(0)


ln = [int(i) for i in input().split(' ')]
n = ln[0]
m = ln[1]
q = ln[2]
s = input()
t = input()

def runAns(s, t):
	ss = 0
	sso = [0] * (len(t) - 1)
	for i in range(0, n - len(t) + 1):
		f = True
		for j in range(0, n - i):
			if j >= len(t):
				break
			if s[i + j] != t[j]:
				f = False
				break
		if f:
			ss += 1
		sso.append(ss)
	return [ss, sso]
o = runAns(s, t)
ss = o[0]
o1 = o[1]
o = runAns(''.join(list(s)[::-1]), ''.join(list(t)[::-1]))
o2 = o[1][::-1]
for i in range(0, q):
	ln = [int(j) for j in input().split(' ')]
	n1 = ln[0]
	n2 = ln[1]
	print(max(0, o2[n1 - 1] + o1[n2 - 1] - ss))


f = lambda : map(int, input().split())
(n, m, q) = f()
s = input()
sb = input()
indexes = ''
for i in range(n - m + 1):
	sec_i = i + m
	if s[i:sec_i] == sb:
		indexes += '1'
	else:
		indexes += '0'
for j in range(q):
	(l, r) = f()
	l -= 1
	print(indexes[l:max(r - m + 1, 0)].count('1'))


(n, m, q) = map(int, input().split())
s = input()
s1 = input()
st = []
en = []
l = []
for i in range(n):
	st.append(0)
	en.append(0)
for i in range(n):
	if s[i:i + len(s1)] == s1:
		l.append(1)
		st[i] = 1
		en[i + len(s1) - 1] = 1
	else:
		l.append(0)
sums = 0
sume = 0
sa = []
se = []
a = []
for i in range(n):
	sums = sums + st[i]
	sume = sume + en[i]
	sa.append(sums)
	se.append(sume)
for i in range(q):
	(a1, b1) = map(int, input().split())
	if a1 == 1:
		print(se[b1 - 1] - 0)
	elif se[b1 - 1] - sa[a1 - 2] < 0:
		print(0)
	else:
		print(se[b1 - 1] - sa[a1 - 2])


(n, m, q) = map(int, input().split())
s = input()
t = input()
pat = [0] * n
i = 0
c = 0
while True:
	f = s[i:].find(t)
	if f == -1:
		for j in range(i, n):
			pat[j] = c
		break
	g = i + f
	for j in range(i, g):
		pat[j] = c
	c += 1
	pat[g] = c
	i = g + 1
pat = [0] + pat
for _ in range(q):
	(l, r) = map(int, input().split())
	if r - l + 1 >= m:
		print(pat[r - m + 1] - pat[l - 1])
	else:
		print(0)


(n, m, q) = list(map(int, input().split()))
s = input()
t = input()
ts = [1 if s[i:i + len(t)] == t else 0 for i in range(len(s) - len(t) + 1)] + [0] * (len(t) - 1)
sums = [[0 for i in range(len(s))] for i in range(len(s))]
for i in range(n):
	sums[i][i] = ts[i]
for i in range(n):
	for j in range(i + 1, n):
		sums[i][j] = sums[i][j - 1] + ts[j]
for i in range(q):
	(l, r) = list(map(int, input().split()))
	if r - m < 0:
		print(0)
	else:
		print(sums[l - 1][r - m])


import sys
out = sys.stdout
(n, m, q) = map(int, input().split())
s = input()
t = input()
res = []
for i in range(n - m + 1):
	if s[i:i + m] == t:
		e = (i, i + m - 1)
		res.append(e)
for i in range(q):
	(li, ri) = map(int, input().split())
	k = 0
	for (t, p) in res:
		if t >= li - 1 and p <= ri - 1:
			k += 1
	out.write(str(k) + '\n')


import re
import bisect

def preprocess(s, t):
	starts = []
	ends = []
	l = len(t)
	for m in re.finditer('(?=%s)' % t, s):
		starts.append(m.start() + 1)
		ends.append(m.start() + l)
	return (starts, ends)

def run(l, r, starts, ends):
	lpos = bisect.bisect_left(starts, l)
	rpos = bisect.bisect_right(ends, r)
	tt = rpos - lpos
	return tt if tt >= 0 else 0

def main():
	(n, m, q) = map(int, input().split())
	s = input()
	t = input()
	(starts, ends) = preprocess(s, t)
	for _ in range(q):
		(l, r) = map(int, input().split())
		print(run(l, r, starts, ends))
main()


(n, m, q) = [int(x) for x in input().split()]
s = input()
t = input()
li = []
for i in range(q):
	(a, b) = input().split()
	li.append([int(a) - 1, int(b) - 1])
dp = []
for i in range(n - m + 1):
	if s[i:i + m] == t:
		dp.append(1)
	else:
		dp.append(0)
for i in li:
	if i[1] - i[0] < m - 1:
		print(0)
	else:
		print(sum(dp[i[0]:i[1] - m + 2]))


from sys import stdin

def main():
	(n, m, q) = map(int, input().split())
	(s, t) = (input(), input())
	field = []
	(i, j, c) = (-1, 0, 0)
	m -= 1
	while True:
		j = s.find(t, i + 1)
		if j != -1:
			field += [c] * (j - i)
			i = j
			c += 1
		else:
			field += [c] * (n - i + 1)
			break
	res = stdin.read().splitlines()
	for (i, s) in enumerate(res):
		(l, r) = map(int, s.split())
		l -= 1
		r -= m
		res[i] = str(field[r] - field[l] if l <= r else 0)
	print('\n'.join(res))
main()


(n, m, q) = map(int, input().split(' '))
text = list(input())
patt = list(input())
cnt = [0 for i in range(n)]
if m > n:
	for i in range(q):
		(l, r) = map(int, input().split(' '))
		print(0)
else:
	for i in range(n):
		if i + m > n:
			break
		if text[i:i + m] == patt:
			cnt[i] += 1
	for i in range(1, n):
		cnt[i] = cnt[i] + cnt[i - 1]
	for i in range(q):
		(l, r) = map(int, input().split(' '))
		l -= 1
		r -= 1
		r = r - m + 1
		if l > r:
			print(0)
		elif l != 0:
			print(cnt[r] - cnt[l - 1])
		else:
			print(cnt[r])