Самый длинный палиндром в строке с использованием дерева суффиксов

Question

Я пытался найти самый длинный палиндром в строке. Решение по грубой силе занимает O (n ^ 3) времени. Я прочитал, что для него существует линейный алгоритм времени, использующий суффиксные деревья. Я знаком с суффиксными деревьями и мне удобно строить их. Как вы используете встроенное суффиксное дерево, чтобы найти самый длинный палиндром.

Answer 1

Линейное решение можно найти следующим образом: *

Пререквизиты:

(1). Вы должны знать, как построить массив суффиксовза O (N) или O (NlogN).

(2). Вы должны знать, как найти стандартный массив LCP, т.е.LCP между смежными суффиксами i и i-1

т.е.LCP [i] = LCP (суффикс i в отсортированном массиве, суффикс i-1 в отсортированном массиве) для (i> 0).

Пусть S будет исходной строкой, а S ' будет обратным к исходной строке.Для примера возьмем S = " banana ".Тогда его обратная строка S '= ananab.

Шаг 1 : объединить S + # + S ', чтобы получить String Str, где # - алфавит, отсутствующий в исходной строке.

    Concatenated String Str=S+#+S'
    Str="banana#ananab"

Шаг 2: Теперь создайте суффиксный массив строки Str.

В этом примере массив суффиксов:

Suffix Number   Index   Sorted Suffix
0               6       #ananab
1               5       a#ananab
2               11      ab
3               3       ana#ananab
4               9       anab
5               1       anana#ananab
6               7       ananab
7               12      b
8               0       banana#ananab
9               4       na#ananab
10              10      nab
11              2       nana#ananab
12              8       nanab

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

То есть SuffixArray [] = {6,5,11,3,9,1,7,12,0,4,10,2,8};

Шаг 3 : Как вам удалосьСоздайте массив суффиксов, теперь найдите Самые длинные общие префиксы между смежными суффиксами .

LCP between #ananab        a#ananab          is :=0
LCP between a#ananab       ab                is :=1
LCP between ab             ana#ananab        is :=1
LCP between ana#ananab     anab              is :=3
LCP between anab           anana#ananab      is :=3
LCP between anana#ananab   ananab            is :=5
LCP between ananab         b                 is :=0
LCP between b              banana#ananab     is :=1
LCP between banana#ananab  na#ananab         is :=0
LCP between na#ananab      nab               is :=2
LCP between nab            nana#ananab       is :=2
LCP between nana#ananab nanab                is :=4

Таким образом, массив LCP LCP = {0,0,1,1,3,3,5,0,1,0,2,2,4}.

Где LCP [i] = длина наибольшего общего префикса между суффиксом i и суффиксом (i-1).(для i> 0)

Шаг 4:

Теперь вы создали массив LCP. Используйте следующую логику.

    Let the length of the Longest Palindrome ,longestlength:=0 (Initially)
    Let Position:=0.
    for(int i=1;i<Len;++i)
    {
        //Note that Len=Length of Original String +"#"+ Reverse String
        if((LCP[i]>longestlength))
        {
            //Note Actual Len=Length of original Input string .
            if((suffixArray[i-1]<actuallen && suffixArray[i]>actuallen)||(suffixArray[i]<actuallen && suffixArray[i-1]>actuallen))
            {
                 //print :Calculating Longest Prefixes b/w suffixArray[i-1] AND  suffixArray[i]


                longestlength=LCP[i];
              //print The Longest Prefix b/w them  is ..
              //print The Length is :longestlength:=LCP[i];
                Position=suffixArray[i];
            }
        }
    }
    So the length of Longest Palindrome :=longestlength;
    and the longest palindrome is:=Str[position,position+longestlength-1];

ВыполнениеПример ::

    actuallen=Length of banana:=6
    Len=Length of "banana#ananab" :=13.

Calculating Longest Prefixes b/w a#ananab AND  ab
The Longest Prefix b/w them  is :a 
The Length is :longestlength:= 1 
Position:= 11




Calculating Longest Prefixes b/w ana#ananab AND  anab
The Longest Prefix b/w them  is :ana
The Length is :longestlength:= 3 
Position:=9



Calculating Longest Prefixes b/w anana#ananab AND  ananab
The Longest Prefix b/w them  is :anana
The Length is :longestlength:= 5 
Position:= 7

So Answer =5.
And the Longest Palindrome is :=Str[7,7+5-1]=anana

Просто сделайте заметку ::

Условие if в шаге 4 в основном означает, что в каждой итерации (i), если я берузатем суффиксы s1 (i) и s2 (i-1): «s1 должен содержать #, а s2 не должен содержать #« ИЛИ »s2 должен содержать # и s1 не должен содержать #».

 |(1:BANANA#ANANAB)|leaf
tree:|
     |     |      |      |(7:#ANANAB)|leaf
     |     |      |(5:NA)|
     |     |      |      |(13:B)|leaf
     |     |(3:NA)|
     |     |      |(7:#ANANAB)|leaf
     |     |      |
     |     |      |(13:B)|leaf
     |(2:A)|
     |     |(7:#ANANAB)|leaf
     |     |
     |     |(13:B)|leaf
     |
     |      |      |(7:#ANANAB)|leaf
     |      |(5:NA)|
     |      |      |(13:B)|leaf
     |(3:NA)|
     |      |(7:#ANANAB)|leaf
     |      |
     |      |(13:B)|leaf
     |
     |(7:#ANANAB)|leaf

Answer 2

Полагаю, вам нужно действовать следующим образом:

Пусть y ₁ y ₂ ... y _n будет вашей строкой (где y _я - буквы).

Создать обобщенное суффиксное дерево из S _f = y ₁ y ₂ ... y _n $ и S _r = y _n y _{n - 1} ... y ₁ # (поменять буквыи выберите различные конечные символы для S _f ($) и S _r (#)) ... где S _f обозначает «Строка, Вперед» и S _r обозначает «Строка, Реверс» .

Для каждого суффикса i в S _f найти tСамый низкий общий предок с суффиксом n - i + 1 в S _r .

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

(1) Префикс суффикса является подстрокой .

(2) A палиндром - строка, идентичная ее обратному.

(3) Таким образом, самый длинный содержащийся в строке палиндром - это самая длинная общая подстрока этой строки и ее обратного.

(4) Таким образом, самый длинный содержащийся палиндром в строке является точно самым длинным общим префиксом из всех пар суффиксов между строкой и ее обратным знаком.Вот что мы здесь делаем.

ПРИМЕР

Давайте возьмем слово банан .

S _f = банан $

S _r = ananab #

Ниже приведено обобщенное дерево суффиксов S _f и S _r , где число в конце каждого пути является индексом соответствующего суффикса.Есть небольшая ошибка: a , общий для всех трех ветвей родителя Blue_4, должен находиться на его входном крае, рядом с n :

Самый низкий внутренний узел в дереве - самая длинная общая подстрока этой строки и ее обратная сторона.Глядя на все внутренние узлы дерева, вы обнаружите самый длинный палиндром.

Самый длинный палиндром находится между Green_0 и Blue_1 (то есть банан и анана ) и анана

---

РЕДАКТИРОВАТЬ

Я только что нашел эту статью , которая отвечает на этот вопрос.

Answer 3

Несколько лет спустя ...

Предположим, s - исходная строка, а r - s в обратном порядке. Давайте также предположим, что мы полностью построили дерево суффиксов ST, используя s.

Наш следующий шаг - проверить все суффиксы r против ST. С каждым новым суффиксом r мы будем вести подсчет первых k символов, которые мы успешно сопоставили с существующим суффиксом в дереве (т. Е. Одним из суффиксов s).

Например, скажем, мы сопоставляем суффикс "RAT" из r, а s содержит некоторые суффиксы, начинающиеся с "RA" , но не такие, которые "RAT" . k будет равно 2, когда нам, наконец, придется отказаться от надежды на финальные символы "T" . Мы сопоставили первые два символа суффикса r с первыми двумя символами суффикса s. Мы назовем этот узел, которого мы достигли n.

Теперь, как мы узнаем, когда нашли палиндром? Проверяя все конечные узлы в n.

В традиционном дереве суффиксов начальный индекс каждого суффикса сохраняется в листовом узле этой ветви суффикса. В приведенном выше примере s может содержать набор суффиксов, начинающихся с «RA» , каждый из которых начинается с одного из индексов, присутствующих в потомках конечного узла n.

Давайте использовать эти индексы.

Что это значит, если мы сопоставим k символов одной из подстрок R с k символами в ST? Ну, это просто означает, что мы нашли некоторую строку перевернутой. Но что это значит, если место, где начинается подстрока в R, совпадает с совпадающей подстрокой в ​​S плюс k? Да, это означает, что s[i] through s[i+k] читается так же, как s[i+k] through s[i]! Итак, для определения мы нашли палиндром размером k.

Теперь все, что вам нужно сделать, это сохранить вкладку на самом длинном палиндроме, найденном до сих пор, и вернуть ее в конце вашей функции.

Answer 4

Простое и краткое объяснение из Skiena - The Algorithm Design Manual

Найдите самый длинный палиндром в S [с использованием дерева суффиксов] - палиндром - это строка, которая читает то же самоеесли порядок символов обратный, такой как madam .Чтобы найти самый длинный палиндром в строке S, создайте одно суффиксное дерево, содержащее все суффиксы S и обращение S, с каждым листом, идентифицированным по его начальной позиции.Палиндром определяется любым узлом в этом дереве, у которого есть прямые и обратные дочерние элементы из одной и той же позиции.

Answer 5

DP решение:

int longestPalin(char *str)
{
    n = strlen(str);
    bool table[n][n]l
    memset(table, 0, sizeof(table));
    int start = 0;

    for(int i=0; i<n; ++i)
        table[i][i] = true;
    int maxlen = 1;

    for(int i=0; i<n-1; ++i)
    {
        if(str[i] == str[i+1])
        {
            table[i][i] = true;
            start = i;
            maxlen = 2;
        }
    }

    for(int k=3; k<=n; ++k)
    {
        for(int i=0; i<n-k+1; ++i)
        {
            int j = n+k-1;
            if(str[i] == str[j] && table[i+1][j-1])
            {
                table[i][j] = true;
                if(k > maxlen)
                {
                    start = i;
                    maxlen = k;
                }
            }
        }
    }
    print(str, start, start+maxlen-1);
    return maxlen;
}