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

本文介绍了使用后缀树最长回文的字符串的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图找到最长的回文中的字符串。该蛮力解决方案需要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 y1y2 ... yn be your string (where yi are letters).

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

Create the generalized suffix tree of Sf = y1y2 ... yn$ and Sr = ynyn - 1 ... y1# (reverse the letters and choose different ending characters for Sf ($) and Sr (#))... where Sf stands for "String, Forward" and Sr stands for "String, Reverse".

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

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

什么从根到运行这个最低的共同祖先是一个回文，因为现在最低的共同祖先重新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 =香蕉$ 的

Sf = banana$

取值研究 = ananab＃的

Sr = ananab#

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

Below is the generalised suffix tree of Sf and Sr, 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.