Какова сложность алгоритма поиска подстроки в строке, и как она подсчитана? Прошу объяснить. (алгоритм сыроват, но упрощён в качестве примера и для понимания)
text='bla-bla-this-bla'
subtext='this'
for i,element in enumerate(text):
if element == subtext[0]:
if subtext == text[i:i+len(subtext)]:
print(i)
Анонимный пользователь Изменен статус публикации
Пусть:
n = len(text) m = len(subtext)
Очевидно что цикл for сделает в худшем случае n итераций, внутри каждой итерации в худшем случае мы делаем слайс text[i:i+len(subtext)], который выполняется за O(m), а затем сравнение за те же O(m), в итоге получаем O(nm).
Напишите ваш ответ.