在使用后缀树的string中最长的回文

我试图find一个string中最长的回文。 powershell解决scheme需要O（n ^ 3）时间。 我读了使用后缀树有一个线性时间algorithm。 我熟悉后缀树，并且很舒适地构build它们。 你如何使用内置的后缀树find最长的回文。

Answer 1

我相信你需要这样做：

让y ₁ y ₂ … y _n是你的string（其中y _i是字母）。

创buildS _f = y ₁ y ₂ … y _n $和S _r = y _n y _{n – 1} … y ₁ ＃的广义后缀树（反转字母并为S _f （$）select不同的结束字符和S _r （＃））…其中S _f代表“String，Forward” ， S _r代表“String，Reverse” 。

对于S _f中的每个后缀i ，findS _r中具有后缀n – i + 1的最低共同祖先。

从根到最低的共同祖先是回文，因为现在最低的共同祖先代表了这两个后缀中最长的共同前缀。 回想起那个：

（1） 后缀的前缀是子串 。

（2） 回文是与其相反的string。

（3）因此，一个string中最长的包含回文是恰好是该string中最长的公共子string及其相反的string。

（4）因此，一个string中包含的最长的回文正好是string与其反向之间的所有后缀对中最长的公共前缀 。 这是我们在这里做的。

例

让我们把香蕉这个词。

S _f =香蕉$

S _r = ananab＃

下面是S _f和S _r的广义后缀树，其中每个path末尾的数字是相应后缀的索引。 有一个小错误，Blue_4父母的所有3个分支的一个共同点应该在它的进入边缘，在n ：

树中最低的内部节点是这个string中最长的公共子string及其相反。 查看树中的所有内部节点，您将因此find最长的回文。

最长的回文在Green_0和Blue_1之间find（即香蕉和anana ）并且是anana

---

编辑

我刚刚发现这篇文章回答了这个问题。

Answer 2

线性解决scheme可以通过这种方式find::

Prequisities：

（1）。 您必须知道如何在O（N）或O（NlogN）时间构造后缀数组。

（2）。 你必须知道如何find标准的LCP数组，即。 相邻的后缀i和i-1之间的LCP

即， 对于（i> 0），LCP [i] = LCP（在sorting数组中后缀i，在sorting数组中后缀i-1）。

设S为原始string， S'为原始string的反向。 让我们以S =“ 香蕉 ”为例。 然后它的反向串S'= ananab。

步骤1 ：连接S +＃+ S'以获得String Str，其中＃是原始string中不存在的字母表。

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

第2步：现在构造stringStr的后缀数组。

在这个例子中，后缀数组是：

 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 

请注意，后缀数组是一个整数数组，以字典顺序给出string后缀的起始位置。因此，包含起始位置索引的数组是一个后缀数组。

那就是SuffixArray [] = {6,5,11,3,9,1,7,12,0,4,10,2,8};

第3步 ：正如你已经设法构造后缀数组，现在find相邻后缀之间的最长公共前缀 。

 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 

因此LCParraysLCP = {0,0,1,1,3,3,5,0,1,0,2,2,4}。

其中LCP [i] =后缀i和后缀（i-1）之间的最长公共前缀的长度。 （对于i> 0）

步骤4：

现在你已经构build了一个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/wa#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 

只是做一个注释::

步骤4中的if条件基本上是指在每次迭代（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 3

迟了几年…

假设s是原始string， r是反转的。 我们还假设我们已经完全使用s构build了一个后缀树ST 。

我们的下一步是检查ST对所有的后缀。 对于每个新的后缀r ，我们将保持一个计数，我们已经成功地匹配了树中预先存在的后缀（即， s的后缀之一）匹配的前k字符。

举个例子，假设我们匹配来自r的后缀“RAT” ，并且s包含一些以“RA”开头的后缀，但没有匹配“RAT”的后缀。 当我们终于不得不放弃对最后字符“T”的希望时， k将等于2。 我们将r后缀的前两个字符与s后缀的前两个字符进行匹配。 我们将调用我们到达的节点。

现在，我们怎么知道什么时候find了回文？ 通过检查n下的所有叶子节点。

在传统的后缀树中，每个后缀的起始索引存储在该后缀分支的叶节点处。 在我们上面的例子中， s可能包含了一堆从“RA”开始的后缀，每个后缀都从n的叶子节点后​​代中的一个索引处开始。

我们来使用这些指标。

如果我们将一个R的子串中的k字符与ST中的k字符进行匹配，意味着什么？ 那么，这只是意味着我们发现了一些string颠倒 但是，如果子string在R开始的位置等于S + k匹配的子string，那么这意味着什么？ 是的，这意味着s[i] through s[i+k]读取与s[i+k] through s[i]相同！ 所以，定义我们已经find一个大小为k的回文。

现在，您所要做的就是在最长的回文中保留一个标签，并在函数结束时返回。

Answer 4

Skiena - The Algorithm Design Manual简单和简单的解释Skiena - The Algorithm Design Manual

findS中最长的回文[使用后缀树] – 回文是一个string，如果字符的顺序相反， 如夫人，则这个string是相同的。 要查找stringS中最长的回文，build立一个包含所有S后缀和S的逆转的单个后缀树，每个叶子由其起始位置标识。 回文是由树中的任何节点定义的，它具有从相同位置向前和颠倒儿童。

Answer 5

DP解决scheme：

 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; }