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

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

Предварительные требования:

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

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

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

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

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

    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

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

Это 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

С опозданием на несколько лет ...

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

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

В качестве примера предположим, что мы сопоставляем суффикс "RAT" с r, а s содержал некоторые суффиксы, начинающиеся с "RA", но ни один из которых не соответствовал " КРЫСА ". 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.

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

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

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