使用后缀树的字符串中最长的回文

Question

我试图在字符串中找到最长的回文.蛮力解决方案需要O(n ^ 3)时间.我读到有一个使用后缀树的线性时间算法.我熟悉后缀树,很舒服地建造它们.如何使用构建的后缀树找到最长的回文.

Answer 1

线性解决方案可以通过以下方式找到::

Prequisities:

(1).您必须知道如何在O(N)或O(NlogN)时间内构造后缀数组.

(2).您必须知道如何找到标准LCP阵列即.相邻后缀i和i-1之间的LCP

即.对于(i> 0),LCP [i] = LCP(排序数组中的后缀i,排序数组中的后缀i-1).

设S为原始字符串,S'与原始字符串相反.让我们以S =" banana "为例.然后它的反向字符串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

请记下::

步骤4中的if条件基本上是指,在每次迭代(i)中,如果我取后缀s1(i)和s2(i-1)那么,"s1必须包含#,而s2必须不包含#"OR"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 _i是字母).

创建S _f = y ₁ y ₂ ... y _n $和S _r = y _n y _{n - 1} ... y ₁#的广义后缀树(反转字母并为S _f($)选择不同的结束字符和S _r(#))...其中S _f代表"String,Forward",S _r代表"String,Reverse".

对于每一个后缀我在小号_˚F,找到后缀最低的共同祖先N -我+ 1的小号_[R .

什么从根到最低共同祖先是回文,因为现在最低的共同祖先代表这两个后缀的最长共同前缀.回想起那个:

(1)一种前缀一个的后缀是一个子串.

(2)回文是与其反向相同的字符串.

(3)因此,字符串中包含的最长的回文恰好是该字符串的最长公共子字符串及其相反的字符串.

(4)因此,字符串中包含的最长的回文正好是字符串与其反向之间所有后缀对的最长公共前缀.这就是我们在这里所做的.

例

我们来取一个单词banana.

S _f =香蕉$

S _r = ananab#

下面是S _f和S _r的通用后缀树,其中每个路径末尾的数字是相应后缀的索引.有一个小错误,一个通用于所有Blue_4父级的3个分支应成为其进入边缘,旁边ñ:

树中最低的内部节点是该字符串的最长公共子字符串,反之亦然.通过查看树中的所有内部节点,您将找到最长的回文结构.

最长的回文位于Green_0和Blue_1(即香蕉和anana)之间,并且是anana

编辑

我刚刚发现这篇论文回答了这个问题.

Answer 3

几年后......

假设s是原始字符串,并且r是s相反的.我们还假设我们已经完全ST使用了后缀树s.

我们的下一个步骤是检查的所有后缀r反对ST.对于每个新的后缀r,我们将保持k我们成功匹配的第一个字符与树中预先存在的后缀(即s后缀之一)的计数.

作为一个例子,说我们相匹配的后缀"老鼠仓"的r,并s包含有开头有一些后缀"RA",但没有相匹配的"老鼠仓".k当我们最终不得不放弃对最终字符"T"的希望时,它将等于2 .我们将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.

现在,您所要做的就是在目前为止发现的最长的回文上留下一个标签,并在功能结束时返回它.