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

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

    我相信你需要这样做:

    y 1 y 2y n是你的string(其中y i是字母)。

    创buildS f = y 1 y 2y n $S r = y n y n – 1y 1 的广义后缀树(反转字母并为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 fS r的广义后缀树,其中每个path末尾的数字是相应后缀的索引。 有一个小错误,Blue_4父母的所有3个分支的一个共同点应该在它的进入边缘,在n

    在这里输入图像说明

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

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


    编辑

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

    线性解决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 

    迟了几年…

    假设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的回文。

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

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

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

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