Изменения

Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного двоичного поиска. Во-первых, хеширование подстрок строки <tex>s</tex> и запись их в Set требует <tex>O(|s|)</tex> шагов. Во-вторых, хеширование подстрок строки <tex>t</tex> и проверка их наличия в Set требует <tex>O(|t|)</tex>. Проверка на совпадение нескольких символов подстрок требует константное время. Значит,на каждый шаг бинарного двоичного поиска требуется <tex>O(max(|s|, |t|))</tex> действий. Заметим, что всего для завершения бинарного двоичного поиска потребуется <tex>O(\log(\min(|s|, |t|)))</tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(|s|, |t|)) \cdot \max(|s|, |t|))</tex> действий.