Почему второй код быстрее?

На вход подается строка 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)
  • Вопрос задан
  • 677 просмотров
Пригласить эксперта
Ответы на вопрос 4
На беглый взгляд из-за разной сложности алгоритма. Смотрите, в первом цикл в цикле - похоже, что там квадратическая сложность. Второй - линейная. Гуглите по этим терминам.

https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D...
Ответ написан
t0rr
@t0rr
PM
Решение в 1 строку:
result = s[l-1:r].count(t)
Ответ написан
Stalker_RED
@Stalker_RED
Какие операции тяжелые и какие легкие в обеих вариантах?
Безусловно, определять такие операции "на глаз" - это очень крутой скилл, но его довольно сложно прокачать.

Те, кто пока не прокачал могут воспользоваться одним из профилировщиков.
Профайлер покажет сколько раз вызывались ваши функции, сколько времени занял каждый вызов и сколько получилось в итоге.
https://www.youtube.com/watch?v=QJwVYlDzAXs&featur...
Ответ написан
Комментировать
sergovoy
@sergovoy
Студент, учусь в Самарском Университете на ФММ'21
Предлагаю ознакомиться с моим решением данной задачи (https://codeforces.com/contest/1016/problem/B) по ссылке: https://codeforces.com/contest/1016/submission/41169503

Решение получилось самым быстрым среди других решений на третьем Питоне, проверить можно тут: https://codeforces.com/contest/1016/status/B/page/... (необходимо выбрать язык Python 3 в фильтре статуса)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы