Я пытался найти самый длинный палиндром в строке. Решение грубой силы принимает O (n ^ 3) время. Я читал, что для него используется алгоритм линейного времени с использованием суффиксов. Я знаком с суффиксными деревьями, и мне удобнее их строить. Как вы используете построенное дерево суффиксов, чтобы найти самый длинный палиндром.
Самый длинный палиндром в строке с использованием дерева суффиксов
Ответ 1
Я считаю, что вам нужно действовать следующим образом:
Пусть y 1 y 2... y n будет вашей строкой (где y i - буквы).
Создать обобщенное дерево суффиксов S f= y 1 y 2... y n $и S r= y n y n - 1... y 1 # (отмените буквы и выберите разные конечные символы для S f ($) и S r (#))... где S f означает "String, Forward" и S r означает "String, Reverse".
Для каждого суффикса я из S f найдите наименьшего общего предка с суффиксом n - я + 1 в S r.
Что происходит от корня до тех пор, пока этот самый низкий общий предок не станет палиндром, потому что теперь самый низкий общий предок представляет собой самый длинный общий префикс этих двух суффиксов. Напомним, что:
(1) Префиксом суффикса является подстрока.
(2) Палиндром представляет собой строку, идентичную ее обратному.
(3) Таким образом, самый длинный содержащий палиндром внутри строки является самой длинной общей подстрокой этой строки и ее обратным.
(4) Таким образом, самый длинный содержащий палиндром внутри строки является самым длинным общим префиксом всех пар суффиксов между строкой и ее обратным. Это то, что мы делаем здесь.
Пример
Возьмем слово банан.
S f= banana $
S r= ananab #
Ниже представлено обобщенное дерево суффиксов S f и S r, где число в конце каждого пути является индексом соответствующего суффикса. Там небольшая ошибка, общая для всех трех ветвей родителя Blue_4 должна находиться на ее краю ввода, рядом с n:
Самая низкая внутренняя часть node в дереве является самой длинной общей подстрокой этой строки и ее обратным. Глядя на все внутренние узлы в дереве, вы, следовательно, найдете самый длинный палиндром.
Самый длинный палиндром обнаружен между зеленым_0 и синим_1 (т.е. бананом и анана) и является anana
ИЗМЕНИТЬ
Я только что нашел эту статью, которая отвечает на этот вопрос.
Ответ 2
Линейное решение можно найти на этом пути::
Prequisities:
(1). Вы должны знать, как построить массив суффикса в O (N) или O (NlogN) времени.
(2). Вы должны знать, как найти стандартный массив LCP, т.е. LCP между смежными суффиксами я и i-1
т.е. LCP [i] = LCP (суффикс я в отсортированном массиве, суффикс i-1 в отсортированном массиве) для (i > 0).
Пусть S - исходная строка, а S ' - обратная сторона оригинальной строки. Давайте возьмем S = " банан" в качестве примера. Тогда его обратная строка 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
Обратите внимание, что массив суффикса представляет собой массив целых чисел, дающий начальные позиции суффиксов строки в лексикографическом порядке. Итак, массив, содержащий индекс начальной позиции, является массивом суффиксов.
Это СуффиксArray [] = {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-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
Ответ 3
Несколько лет спустя...
Предположим, что s - исходная строка, а r - s. Предположим также, что мы полностью построили дерево суффиксов ST, используя s.
Наш следующий шаг - проверить все суффиксы r на ST. С каждым новым суффиксом r мы будем поддерживать подсчет первых k символов, которые мы успешно сопоставили с существующим суффиксом в дереве (т.е. Одним из суффиксов s).
В качестве примера скажем, что мы сопоставляем суффикс "RAT" с r, а s содержит некоторые суффиксы, начинающиеся с "RA", но ни один из них не соответствует "RAT". k равнялся бы 2, когда мы, наконец, должны были отказаться от надежды на финальные символы "Т". Мы сопоставили первые два символа суффикса r с первыми двумя символами суффикса s. Мы назовем это node, что мы достигли n.
Теперь, откуда мы узнаем, когда мы нашли палиндром? Проверяя все листовые узлы под n.
В традиционном дереве суффиксов начальный индекс каждого суффикса сохраняется на листе node этой ветки суффикса. В нашем примере выше s может содержаться множество суффиксов, начинающихся с "RA", каждый из которых начинается с одного из индексов, присутствующих в потомках node листа n.
Используйте эти индексы.
Что это значит, если мы сопоставим символы k одной из r подстрок с символами k в ST? Ну, это просто означает, что мы нашли какую-то строку в обратном порядке. Но что это означает, если место, где начинается подстрока в r, равно согласованной подстроке в s плюс k? Да, это означает, что s[i] through s[i+k] читает то же самое, что и s[i+k] through s[i]! Итак, будь то определение, мы обнаружили палиндром размера k.
Теперь все, что вам нужно сделать, это сохранить вкладку на самом длинном палиндроме, найденном до сих пор, и вернуть ее в конце вашей функции.
Ответ 4
Простое и короткое объяснение от Skiena - The Algorithm Design Manual
Найти самый длинный палиндром в S [с использованием дерева суффиксов]. Палиндром - это строка, которая читает то же самое, если порядок символов отменяется, например, мадам. Чтобы найти самый длинный палиндром в строке S, постройте единое дерево суффиксов, содержащее все суффиксы S и обращение S, причем каждый лист идентифицируется по его исходной позиции. Палиндром определяется любым node в этом дереве, который имеет вперед и назад детей из той же позиции.
Ответ 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;
}