На вход подается строка s и t, числа l,r. Суть задачи в том, что бы найти число вхождений строки t в подстроку из s, где l и r - номера явных границ строки s. То есть l = 1, r = 3, s = '12345', искомая подстрока будет '123'. Число m - длина s.
Первый вариант кода не проходит по времени. Почему? Как мне это видится - число операций в первом варианте не больше, чем во втором, но count() намного быстрее чем цикл со сравнениями. Так ли это? Какие операции тяжелые и какие легкие в обеих вариантах?
n, m, q = [int(i) for i in input().split()]
s = input()
t = input()
for i in range(q):
l,r = map(int, input().split())
count = 0
if r - l + 1 >= m:
for j in range(l-1, r - m + 1):
if s[j:j + m] == t:
count += 1
print(count)
Второй вариант - быстрее
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)
Простой
