Поиск наибольшей общей подстроки двух строк с использованием хеширования

Постановка задачи

Имеются строки [math]s[/math] и [math]t[/math] такие, что элементы этих строк [math]-[/math] символы из конечного алфавита [math] \Sigma [/math]. Говорят, что строка [math]z[1 .. m][/math] является подстрокой строки [math]s[1 .. n][/math], если существует такой индекс [math]k \in [0 .. n - m][/math], что для любого [math]i \in [1 .. m][/math] справедливо [math]s[k + i] = z[i][/math]. Требуется найти такую строку [math]z[/math] максимальной длины, что [math]z[/math] является и подстрокой [math]s[/math], и подстрокой [math]t[/math].

Алгоритм

Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет [math]x[/math]. Заметим, что у строк [math]s[/math] и [math]t[/math] обязательно найдется общая подстрока длины [math]y \in [0 .. x][/math], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию [math]f : [0 .. \min(|s|, |t|)] \rightarrow \{0, 1\}[/math], которая для [math]i[/math] из области определения равна 1, если у строк [math]s[/math] и [math]t[/math] есть общая подстрока длины [math]i[/math], иначе она равна 0. Согласно замечанию, функция [math]f[/math] должна по мере возрастания [math]i[/math] быть равной 1 до некоторого момента, а затем обращаться в 0. Собственно, максимальное значение, при котором функция принимает значение 1, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью бинарного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается использовать хеширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом:
1) у строки [math]s[/math] хешируем подстроки заданной длины и полученные хеши записываем в Set.
2) у строки [math]t[/math] хешируем подстроки заданной длины и в случае совпадения хеша с элементом 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

Время работы

Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки [math]s[/math] и запись их в Set требует [math]O(|s|)[/math] шагов. Во-вторых, хеширование подстрок строки [math]t[/math] и проверка их наличия в Set требует [math]O(|t|)[/math]. В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную [math]O(1)[/math]. Поскольку хешировали с помощью этого метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется [math]O(max(|s|, |t|))[/math] действий. На самом деле требуется несколько больше времени, поскольку совпадение хешей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью [math]O[/math]. Заметим, что всего для завершения бинарного поиска потребуется [math]O(\log(\min(|s|, |t|)))[/math] шагов. Следовательно, суммарное время работы алгоритма будет [math]O(\log(\min(|s|, |t|)) \times \max(|s|, |t|))[/math] действий.

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.