Вычисление самой длинной общей подстроки двух строк с использованием суффиксных массивов

Question

После того, как я узнал, как построить суффиксный массив в сложности $ O (n) $, я заинтересован в обнаружении приложений массивов суффиксов. Одним из них является поиск самой длинной общей подстроки между двумя строками, в $ O (n) $ времени. Я нашел в Интернете следующий алгоритм:

1. объединить две строки $ $ и $ b $ в одну строку $ ab $
2. Вычислить массив суффиксов $ ab $
3. Вычислить массив $ lcp $ (самый длинный общий префикс)
4. Ответ - самая большая стоимость $ lcp [i] $

Я пытался реализовать его, но, как не было сказано много деталей реализации (т. Е. При сожатре строк, должен ли я поставить специальный характер между ними ($ acb $)?), Мой код не удался во многих тестовых случаях. Может ли кто -нибудь подробнее рассказать об этом алгоритме?

Заранее спасибо.

Примечание: Я не гарантирую правильность этого алгоритма; Я нашел это в блоге, и я не уверен, что он работает. Если вы думаете, что это неверно, пожалуйста, предложите другой алгоритм.

Answer 1

Ваш алгоритм есть неверный. Анкет Я предполагаю, что вы знаете, как вычислить массив суффиксов и массив LCP строки, то есть их эффективную реализацию. Как было указано в комментариях, вы должны попытаться понять, что такое каждый компонент и почему он работает.

Прежде всего, это суффиксный массив ($ sa $) строки. Массив суффиксов - это в основном все суффиксы строки $ S $, расположенные в восходящем лексикографическом порядке. В частности, стоимость $ sa [i] $ указывает на то, что суффикс $ s $, начиная с позиции $ sa [i] $, ранжируется $ i $ в лексикографическом упорядочении всех суффиксов $ s $.

Следующим является $ lcp $ массив. $ Lcp [i] $ указывает на длину самой длинной общей префикс между суффиксы Начиная с $ sa [i-1] $ и $ sa [i] $. То есть он отслеживает длину самого длинного распространенного префикса среди двух последовательных суффиксов $ S $ при расположении в лексикографическом порядке.

В качестве примера рассмотрим строку $ s = abbabca $. Суффиксы в лексикографическом порядке будут $ {a, abbabca, abca, babca, bbabca, bca, ca } $, so $ sa = [7, 1, 4, 3, 2, 5, 6] $ для 1 -индексированный массив. Массив $ lcp $ будет $ lcp = [-, 1, 2, 0, 1, 1, 0] $.

Теперь, учитывая две строки $ a $ и $ b $, мы объединяем их как $ s = a #b $, где $ #$ - персонаж, отсутствующий как в $ a $, так и в $ b $. Причина выбора такого персонажа заключается в том, что при вычислении LCP двух суффиксов, скажем, $ ab #dabd $ и $ abd $, сравнение отрывается в конце первой строки (поскольку это происходит только один раз, два Различные суффиксы никогда не будут иметь его в том же положении), и не будет "переполнен" в другую строку.

Теперь можно увидеть, что вы должны понять, почему вам нужно только увидеть последовательные ценности в массиве $ lcp $ (аргумент основан на противоречии и тот факт, что суффиксы в $ sa $ находятся в лексикографическом порядке). Продолжайте проверять массив $ lcp $ на максимальную стоимость так что Сравненные два суффикса не принадлежат к одной и той же исходной строке. Если они не принадлежат к одной и той же оригинальной строке (одна начинается в $ a $, а другая в $ b $), то самая большая такая стоимость - это длина крупнейшей общей подстроки.

В качестве примера рассмотрим $ a = abcabc $ и $ b = bc $. Затем $ s = abcabc #bc $. Сортированные суффиксы - $ {abc #bc, abcabc #bc, bc, bc #bc, bcabc #bc, c, c #bc, cabc #bc } $.
$ begin {Align*} sa & = [4, 1, 8, 5, 2, 9, 6, 3, 7] lcp & = [-, 3, 0, 2, 2, 0, 1, 1 , 0] end {align*} $

Теперь наибольшей стоимостью является $ lcp [2] = 3 $, но это для $ sa [1] $ и $ sa [2] $, оба из которых начинаются в строке $ a $. Итак, мы игнорируем это. С другой стороны, $ lcp [4] = 2 $ для $ sa [3] $ (соответствует суффиксу $ bc $ of $ b $) и $ sa [4] $ (соответствует суффиксу $ bcabc #bc $ $ a $). Таким образом, это самая длинная общая подстроение между двумя строками. Для получения фактической подстроки вы берете длину $ 2 $ (стоимость величайшего достижимый $ Lcp $) подстроение, начиная с $ sa [3] $ или $ sa [4] $, что является $ bc $.

Answer 2

Алгоритм, который вы нашли в Интернете, не совсем правильный. Как упомянуто Пареш, это потерпит неудачу в примере, приведенном им.

Однако, если вы убедитесь, что при проверке LCP вы проверяете только LCP подстроков различных строк. Например, если вы находите LCS Strings A и B, то вам необходимо убедиться, что смежные записи массива суффиксов при проверке на LCP не из одной и той же строки.

Более подробная информация здесь.

Answer 3

Я думаю, что что -то вроде алгоритма, который вы цитируете, действительно должно работать, если персонаж, который не является частью набора символов, используется в качестве разделителя, а массивы суффиксов/префиксов построены в исключать Все строки, которые содержат сепаратор, вероятно, намерение дизайнера. Это в основном эквивалентно строительству суффиксов/массивов префиксов для двух отдельных строк.

Было бы полезно для будущей ссылки, если бы вы разместили ссылку на алгоритм. Обратите внимание, что Википедия имеет алгоритм для этого в псевдокоде и многих других алгоритмах. И есть реализации в большинстве стандартных языков, доступных онлайн.