После того, как я узнал, как построить массив суффиксов в сложности , я заинтересовался открытием приложений массивов суффиксов. Одним из них является нахождение самой длинной общей подстроки между двумя строками за времени. Я нашел в интернете следующий алгоритм:
- объединить две строки и в одну строку
- вычислить массив суффиксов
- вычислить массив (самый длинный общий префикс)
- ответ является наибольшим значением
Я пытался реализовать его, но так как многие детали реализации не были указаны (то есть, при конкатенации строк, должен ли я ставить специальный символ между ними ( )?), Мой код не удался во многих тестовых примерах. Может ли кто-нибудь подробнее остановиться на этом алгоритме?
Заранее спасибо.
Примечание: я не гарантирую правильность этого алгоритма; Я нашел это в блоге, и я не уверен, что это работает. Если вы считаете, что это неверно, предложите другой алгоритм.
algorithms
suffix-array
Ронтогианнис Аристофанис
источник
источник
Ответы:
Ваш алгоритм неверен . Я предполагаю, что вы знаете, как вычислить массив суффиксов и массив LCP строки, то есть их эффективную реализацию. Как было отмечено в комментариях, вы должны попытаться понять, что представляет собой каждый компонент и почему он работает.
Прежде всего, это массив суффиксов ( ) строки. Суффиксный массив - это в основном все суффиксы строки SSA S расположенные в порядке возрастания лексикографии. Более конкретно, значение указывает, что суффикс S, начиная с позиции S A [ i ] , ранжируется i в лексикографическом порядке всех суффиксов SSA[i] S SA[i] i S .
Далее идет массив L C P [ i ] указывает длину самого длинного общего префикса между суффиксами, начиная с S A [ i - 1 ] и S A [ i ] . То есть он отслеживает длину самого длинного общего префикса среди двух последовательных суффиксов SLCP LCP[i] SA[i−1] 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] LCP LCP=[−,1,2,0,1,1,0]
Теперь, учитывая две строки и B , мы объединяем их как S = A # B , где #A B S=A#B # это символ не присутствует в обоих и B . Причина выбора такого символа заключается в том, что при вычислении LCP из двух суффиксов, скажем, a b # dA B и a b dab#dabd а бd , сравнение прервется в конце первой строки (поскольку это происходит только один раз, два разных суффикса никогда не будут иметь его в одной и той же позиции) и не будут «перетекать» в другую строку.
Теперь видно, что вы должны понимать, почему вам нужно видеть только последовательные значения в массиве L C P (аргумент основан на противоречии и том факте, что суффиксы в S A расположены в лексикографическом порядке). Продолжайте проверять L CL Cп SA массив P на максимальное значение, чтобысравниваемые два суффикса не принадлежали к одной и той же исходной строке. Если они не принадлежат одной и той же исходной строке (одна начинается в A, а другая в B ), то наибольшее такое значение - это длина наибольшей общей подстроки.L Cп A В
В качестве примера рассмотрим и B = b c . Тогда S = a b c a b c # b c . Сортированные суффиксы: { a b c # b cA = a b c a b c B=bc S=abcabc#bc . S A{abc#bc,abcabc#bc,bc,bc#bc,bcabc#bc,c,c#bc,cabc#bc}
SALCP=[4,1,8,5,2,9,6,3,7]=[−,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]=3 SA[1] SA[2] A LCP[4]=2 SA[3] bc в ) и S A [ 4 ]B SA[4] (соответствует суффиксу в A ). Итак, это самая длинная общая подстрока между двумя строками. Для получения фактической подстроки вы берете подстроку длины 2 (значение наибольшей из возможных L C P ), начиная с S A [ 3 ] или S A [ 4 ] , то есть b c .bcabc#bc A 2 LCP SA[3] SA[4] bc
источник
{#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]
Алгоритм, который вы нашли в Интернете, не совсем верен. Как упомянул Пареш, это не удастся в приведенном им примере.
Однако, если вы проверяете, что при проверке LCP вы проверяете только LCP подстрок разных строк. Например, если вы находите LCS строк A и B, вам необходимо убедиться, что смежные записи суффиксного массива при проверке LCP не принадлежат одной и той же строке.
Подробнее здесь .
источник
Я думаю, что что-то вроде алгоритма, который вы цитируете, должно действительно работать, если символ, который не является частью набора символов, используется в качестве разделителя, а массивы суффиксов / префиксов построены так, чтобы исключения всех строк, содержащих разделитель, вероятно, намерение дизайнер. это в основном эквивалентно созданию массивов суффиксов / префиксов для двух отдельных строк.
было бы полезно для будущей ссылки, если вы разместили ссылку на алгоритм. обратите внимание, что в википедии есть алгоритм для этого в псевдокоде и многих других алгоритмах. и есть реализации на большинстве стандартных языков, доступных онлайн.
источник