我试图在一个字符串中找到最长的回文。蛮力解决方案需要 O(n^3) 时间。我读到有一个使用后缀树的线性时间算法。我熟悉后缀树并且很乐意构建它们。你如何使用构建的后缀树来找到最长的回文。
问问题
27367 次
5 回答
31
可以通过这种方式找到线性解决方案::
先决条件：
(1)。您必须知道如何在 O(N) 或 O(NlogN) 时间内构建后缀数组。
(2)。您必须知道如何找到标准的 LCP 阵列，即。相邻后缀 i 和 i-1 之间的 LCP
IE 。LCP[i]=LCP(排序数组中的后缀i，排序数组中的后缀i-1)为(i>0)。
令S为原始字符串，S'为原始字符串的倒数。让我们以 S=" banana " 为例。然后它的反向字符串 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
请注意，后缀数组是一个整数数组，它按字典顺序给出字符串后缀的起始位置。因此，保存起始位置索引的数组是后缀数组。
即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
于 2012-06-29T09:07:21.460 回答
25
我相信你需要这样做：
让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中的每个后缀i，在S r中找到后缀为 n - i + 1的最低共同祖先。
从词根到这个最低的共同祖先是回文，因为现在最低的共同祖先代表这两个后缀中最长的共同前缀。回想起那个：
(1)后缀的前缀是子串。
(2)回文串是与其反向相同的字符串。
(3) 因此，一个字符串中最长包含的回文恰好是该字符串的最长公共子串及其相反。
(4) 因此，字符串中包含的最长回文恰好是字符串及其反转之间的所有后缀对中最长的公共前缀。这就是我们在这里所做的。
例子
让我们以香蕉这个词为例。
S f = 香蕉$
S r = ananab#
下面是S f和S r的广义后缀树，其中每条路径末尾的数字是对应后缀的索引。有一个小错误， Blue_4 父级的所有 3 个分支的共同点 a 应该在其进入边缘，在n旁边：
树中最低的内部节点是该字符串的最长公共子字符串及其反向。因此，查看树中的所有内部节点，您会发现最长的回文。
最长的回文出现在 Green_0 和 Blue_1 之间（即，banana和anana），并且是anana
编辑
我刚刚发现这篇论文可以回答这个问题。
于 2011-08-12T18:30:27.763 回答
7
晚了几年...
假设s是原始字符串，并且r是s反向的。我们还假设我们已经ST使用s.
我们的下一步是检查r反对的所有后缀ST。对于 的每个新后缀r，我们将保持与树中已存在的后缀（即' 后缀k之一）成功匹配的第一个字符的计数。s
例如，假设我们要匹配 的后缀"RAT"，r并且包含一些以"RA"s开头的后缀，但没有匹配"RAT"的后缀。当我们最终不得不放弃对最终字符"T"的希望时，将等于 2 。我们将' 后缀的前两个字符与' 后缀的前两个字符进行匹配。我们将调用这个我们到达的节点。krsn
现在，我们怎么知道我们什么时候找到了回文？通过检查下的所有叶节点n。
在传统的后缀树中，每个后缀的起始索引存储在该后缀分支的叶节点上。在我们上面的示例中，s可能包含一堆以"RA"开头的后缀，每个后缀都从 的叶节点后代中存在的一个索引开始n。
让我们使用这些索引。
如果我们将' 子字符串k之一的字符与中的字符进行匹配，这意味着什么？好吧，这只是意味着我们发现了一些颠倒的字符串。但是，如果子字符串开始的位置等于plus中的匹配子字符串，这意味着什么？是的，这意味着读取与! 因此，定义我们已经找到了一个大小为 的回文。 RkSTRSks[i] through s[i+k]s[i+k] through s[i]k
现在，您所要做的就是在迄今为止发现的最长回文上保留一个标签，并在函数结束时将其返回。
于 2015-01-08T03:46:04.357 回答
2
简单而简短的解释来自Skiena - The Algorithm Design Manual
查找 S 中最长的回文 [使用后缀树] -回文是一个字符串，如果字符顺序颠倒，则读取相同，例如madam。为了在字符串 S 中找到最长的回文，构建一个包含 S 的所有后缀和 S 的反转的单个后缀树，每个叶子都由它的起始位置标识。回文由该树中具有来自同一位置的正向和反向子节点的任何节点定义。
于 2014-11-01T12:31:16.993 回答
-2
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;
}
于 2014-01-06T19:11:55.753 回答