Изменения

==Время работы==

Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки <tex>S</tex> и запись их в Set требует O(len(<tex>S</tex>)) шагов. Во-вторых, хеширование подстрок строки <tex>T</tex> и проверка их наличия в Set требует O(len(<tex>T</tex>)). В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную O(1). Поскольку хешировали с помощью [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется O(max(len(<tex>S</tex>), len(<tex>T</tex>))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хешей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью O. Заметим, что всего для завершения бинарного поиска потребуется O(log(min(len(<tex>S</tex>), len(<tex>T</tex>)))) шагов. Следовательно, суммарное время работы алгоритма будет O(log(min(len(<tex>S</tex>), len(<tex>T</tex>))) * max(len(<tex>S</tex>), len(<tex>T</tex>))) действий.