使用后缀树最长回文的字符串 [英] Longest palindrome in a string using suffix tree

问题描述

我试图找到最长的回文中的字符串。该蛮力解决方案需要O（N ^ 3）的时间。我看有一个线性时间算法，它使用后缀树。我所熟悉的后缀树，很舒服建造它们。你如何使用内置后缀树，找到最长的回文。

I was trying to find the longest palindrome in a string. The brute force solution takes O(n^3) time. I read that there is a linear time algorithm for it using suffix trees. I am familiar with suffix trees and am comfortable building them. How do you use the built suffix tree to find the longest palindrome.

推荐答案

我相信你需要采用这种方式：

I believe you need to proceed this way:

让是的<子>的 1 的的是的<子>的 2 的 ... 是的<子>的 N 的是您的字符串（其中的是的<子>的我的是字母）。

Let y₁y₂ ... y_n be your string (where y_i are letters).

创建的取值<子> F = 是的<子>的 1 的 <广义后缀树EM>是的<子>的 2 的 ... 是的<子>的 N 的 $ 和取值<子>研究 = 是的<子>的 N 的的是的<子>的 N - 1 的 ... 是的<子>的 1 的 ＃的（反向的字母和选择适合的取值<子> F 的（$）和取值<子>研究 （＃））...其中的取值<子> F 的代表的字符串，前进和取值<子>研究 的代表的字符串，反的。

Create the generalized suffix tree of S_f = y₁y₂ ... y_n$ and S_r = y_ny_{n - 1} ... y₁# (reverse the letters and choose different ending characters for S_f ($) and S_r (#))... where S_f stands for "String, Forward" and S_r stands for "String, Reverse".

有关每个后缀的我的中的取值<子> F 的，找到最低的共同祖先后缀的 N - 我+ 1 中的取值<子>研究 的。

For every suffix i in S_f, find the lowest common ancestor with the suffix n - i + 1 in S_r.

什么从根到运行这个最低的共同祖先是一个回文，因为现在最低的共同祖先重新presents这两个后缀的最长的共同preFIX。回想一下：

What runs from the root till this lowest common ancestor is a palindrome, because now the lowest common ancestor represents the longest common prefix of these two suffixes. Recall that:

（1）的 preFIX 的的的后缀的是子的。

(1) A prefix of a suffix is a substring.

（2）的回文的是一个字符串，等同于它的反面。

(2) A palindrome is a string identical to its reverse.

（3）因此，一个字符串中包含时间最长的回文，正是这串和其反向的最长公共子。

(3) So the longest contained palindrome within a string is exactly the longest common substring of this string and its reverse.

（4）因此，一个字符串中最长的包含回文是完全最长的共同的 preFIX 的字符串和反向之间的所有成对的后缀的的。这就是我们在这里做。

(4) Thus, the longest contained palindrome within a string is exactly the longest common prefix of all pairs of suffixes between a string and its reverse. This is what we're doing here.

示例

让我们走字的香蕉的。

取值<子> F =香蕉$ 的

S_f = banana$

取值<子>研究 = ananab＃的

S_r = ananab#

下面是广义后缀树的取值<子> F 和取值<子>研究 的，那里的到底有多少每个路径是相应后缀的索引。有一个小错误，的在的共同Blue_4的母公司所有的3个分支应该是其进入边缘，旁边的 N 的：

Below is the generalised suffix tree of S_f and S_r, where the number at the end of each path is the index of the corresponding suffix. There's a small mistake, the a common to all the 3 branches of Blue_4's parent should be on its entering edge, beside n:

在树中的最低内部节点是这个字符串和其反向的最长公共子串。望着树中的所有的内部节点，你会因此找到最长的回文。

The lowest interior node in the tree is the longest common substring of this string and its reverse. Looking at all the interior nodes in the tree you will therefore find the longest palindrome.

最长的回文被发现之间的Green_0和Blue_1之间（即香蕉和阿纳纳的），是的阿纳纳的

The longest palindrome is found between between Green_0 and Blue_1 (i.e., banana and anana) and is anana

修改

我刚刚发现本文，回答了这个问题。

I've just found this paper that answers this question.

这篇关于使用后缀树最长回文的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！