Поиск наибольшей общей подстроки двух строк с использованием хеширования
Постановка задачи
Имеются строки
и такие, что элементы этих строк символы из конечного алфавита . Говорят, что строка является подстрокой строки , если существует такой индекс , что для любого справедливо . Требуется найти такую строку максимальной длины, что является и подстрокой , и подстрокой .Алгоритм
Пусть длина наибольшей общей подстроки будет
1) У строки хешируем подстроки заданной длины и полученные хеши записываем в Set.
2) У строки хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set выполняем посимвольную проверку на совпадение подстрок.
Хеширование будем производить так же, как и в алгоритме Рабина-Карпа.
Псевдокод
findGCS(s, t) n = min(|s|, |t|) left = 0 right = n + 1 while (right - left > 1): val = (left + right) / 2 if (f(val) == 1) left = val else right = val return left
Время работы
Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки
и запись их в Set требует шагов. Во-вторых, хеширование подстрок строки и проверка их наличия в Set требует . Значит,на каждый шаг бинарного поиска требуется действий. Заметим, что всего для завершения бинарного поиска потребуется шагов. Следовательно, суммарное время работы алгоритма будет действий.Литература
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.