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

15

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

  1. объединить две строки A и В в одну строку AВ
  2. вычислить массив суффиксов AВ
  3. вычислить массив LСп (самый длинный общий префикс)
  4. ответ является наибольшим значением LСп[я]

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

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

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

Ронтогианнис Аристофанис
источник
3
Прежде чем реализовать алгоритм, постарайтесь понять, почему он работает. Это может помочь ответить на вопрос, например, как объединить две строки.
Юваль Фильмус
3
Я сомневаюсь в правильности этого алгоритма. Возьмем и б гр д , как я прочитал это будет возвращать в б гр д , что является неправильным. abcdabcdbcdabcd
Хаур

Ответы:

20

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

Прежде всего, это массив суффиксов ( ) строки. Суффиксный массив - это в основном все суффиксы строки SSAS расположенные в порядке возрастания лексикографии. Более конкретно, значение указывает, что суффикс S, начиная с позиции S A [ i ] , ранжируется i в лексикографическом порядке всех суффиксов SSA[i]SSA[i]iS .

Далее идет массив L C P [ i ] указывает длину самого длинного общего префикса между суффиксами, начиная с S A [ i - 1 ] и S A [ i ] . То есть он отслеживает длину самого длинного общего префикса среди двух последовательных суффиксов SLCPLCP[i]SA[i1]SA[i]S когда они расположены в лексикографическом порядке.

В качестве примера рассмотрим строку . Суффиксы в лексикографическом порядке должны быть { a , a b b a b c a , a b c a , b a b c для массива с 1 индексом. Л С РS=abbabca , поэтому S A = [ 7 , 1{a,abbabca,abca,babca,bbabca,bca,ca}.массив будет Ь С Р = [ - , 1 , 2 , 0 , 1 , 1 , 0 ]SA=[7,1,4,3,2,5,6]LCPLCP=[,1,2,0,1,1,0]

Теперь, учитывая две строки и B , мы объединяем их как S = A # B , где #ABS=A#B# это символ не присутствует в обоих и B . Причина выбора такого символа заключается в том, что при вычислении LCP из двух суффиксов, скажем, a b # dAB и a b dab#dabdabd , сравнение прервется в конце первой строки (поскольку это происходит только один раз, два разных суффикса никогда не будут иметь его в одной и той же позиции) и не будут «перетекать» в другую строку.

Теперь видно, что вы должны понимать, почему вам нужно видеть только последовательные значения в массиве L C P (аргумент основан на противоречии и том факте, что суффиксы в S A расположены в лексикографическом порядке). Продолжайте проверять L CLСпSAмассив P на максимальное значение, чтобысравниваемые два суффикса не принадлежали к одной и той же исходной строке. Если они не принадлежат одной и той же исходной строке (одна начинается в A, а другая в B ), то наибольшее такое значение - это длина наибольшей общей подстроки.LСпAВ

В качестве примера рассмотрим и B = b c . Тогда S = a b c a b c # b c . Сортированные суффиксы: { a b c # b cAзнак равноaбсaбсB=bcS=abcabc#bc . S A{abc#bc,abcabc#bc,bc,bc#bc,bcabc#bc,c,c#bc,cabc#bc}
SA=[4,1,8,5,2,9,6,3,7]LCP=[,3,0,2,2,0,1,1,0]

Теперь, наибольшее значение , но это для S A [ 1 ] и S A [ 2 ] , оба из которых начинаются в строке A . Итак, мы игнорируем это. С другой стороны, L C P [ 4 ] = 2 для S A [ 3 ] (соответствует суффиксу b cLCP[2]=3SA[1]SA[2]ALCP[4]=2SA[3]bc в ) и S A [ 4 ]BSA[4](соответствует суффиксу в A ). Итак, это самая длинная общая подстрока между двумя строками. Для получения фактической подстроки вы берете подстроку длины 2 (значение наибольшей из возможных L C P ), начиная с S A [ 3 ] или S A [ 4 ] , то есть b c .bcabc#bcA2 LCPSA[3]SA[4]bc

Paresh
источник
1
Отлично объяснение , но я думаю , что пример немного не так, отсортированные суффиксы: {#bc,abc#bc,abcabc#bc,bc,bc#bc,bcabc#bc,c,c#bc,cabc#bc}, SA=[7,4,1,8,5,2,9,6,3]иLCP=[−,0,3,0,2,2,0,1,1]
Сауль Мартинес Vidals
1

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

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

Подробнее здесь .

rohitjv
источник
1
Когда вы говорите «Этот ответ», вы имеете в виду свой собственный ответ или какой-то другой ответ? Пожалуйста, используйте только поле для ответа, чтобы ответить на вопрос, а не комментировать другие ответы. Когда вы наберете достаточно репутации, вы сможете оставлять комментарии к другим ответам.
Дэвид Ричерби
0

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

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

ВЗН
источник