Почему наивный поиск подстроки даёт TLE и как КМП гарантирует линейность в худшем случае?
Мой наивный поиск подстроки (два вложенных цикла) проходит примеры, но падает по времени на одном тесте. Подозреваю «плохой» тест. Какой это тест, какая у наивного метода сложность в худшем случае и почему КМП от этого застрахован?
2 ответа
Худший тест для наивного поиска — почти-совпадающие строки, где каждое сравнение доходит почти до конца шаблона и срывается на последнем символе. Классика: текст aaaa...a (n штук) и шаблон aaa...ab (m штук). На каждой из ~n позиций вы сравниваете ~m символов → O(n·m), для n=m=10^5 это 10^10 операций = гарантированный TLE.
КМП застрахован, потому что никогда не сравнивает один символ текста дважды «вперёд». При несовпадении он не откатывает указатель текста назад, а сдвигает шаблон по префикс-функции, переиспользуя уже известную информацию о совпавшем префиксе. Указатель i по тексту только растёт; j суммарно увеличивается не больше n раз (амортизация через откаты по pref). Итог — O(n + m) в худшем случае, для любого теста.
// см. kmp_search выше: i не убывает, while-откаты амортизированы O(n)
Именно гарантия «на любом тесте», а не «в среднем», отличает КМП от наивного метода. Хеши тоже дают O(n+m) в среднем, но вероятностно; КМП — детерминированная линейность.
Заметка: на случайных строках наивный поиск работает почти за O(n) (совпадения срываются быстро), поэтому он «проходит примеры». TLE вылезает только на специально подобранном периодичном тесте. Это типичная ловушка — локально быстро, на жюри падает. Если видите ограничение n·m ~ 10^10, сразу не пишите наивно, берите КМП/Z/хеши.