如何找到反向也是子序列的最长连续子序列

问题描述：

假设我有一个序列x1，x2，x3 ..... xn，并且我想找到最长的连续子序列xi，xi + 1，xi + 2 ...... xi + k，其反向也是给定序列的子序列。如果有多个这样的子序列，那么我也必须找到最小的i。如何找到反向也是子序列的最长连续子序列

例如： - 考虑序列：

abcdefgedcg 这里I = 3且k = 2

aabcdddd 这里I = 5，K = 3

我试图寻找在最初的最长公共子序列问题上，但是用来比较两个序列以找到最长的公共子序列....但是这里只有一个序列，我们必须从中找出子序列。请让我知道什么是解决这个问题的最佳方式，以找到最佳解决方案。

我得到I = 2 K =第一个例子是3，第二个例子是i = 5 k = 4。 – Potatoswatter 2010-03-19 04:52:27

@Patatoswatter：不，你不知道。再次阅读该问题的陈述。 “k”的定义已经搞乱了。 k是子字符串*的长度减1，*是基于* 1的*索引。你假设k是子串的长度，我是从开始的距离，但这不是它们被定义的方式。 – 2010-03-19 05:21:34

@Eric：好的。虽然这是有效的，因为他保证为任何非空输入找到子字符串，但仍建议OP使用正常的编程约定。 – Potatoswatter 2010-03-19 05:28:27

答

实际上这是施加到所述序列和其反向的最长公共子串问题：http://en.wikipedia.org/wiki/Longest_common_substring_problem

@Patatoswatter：最长的公共子串问题比较两个字符串来寻找常见的子字符串....我们如何将相同的原则应用于单个序列及其相反？请解释。 – iecut 2010-03-20 02:59:04

@iecut：将序列视为字符串，将其反转为另一个字符串。将算法应用于这两个字符串。您可以在该序列上向后迭代以获得第二个字符串。 – Potatoswatter 2010-03-20 05:35:22

@Patatoswatter它是不是最长的公共子串，因为他要求的子序列，所以我们可以将LCS（只是改变比较）应用到它成为MCS（最小公共子序列）按照字符串和字符串的反向问题 – Peter 2012-10-28 09:44:14

答

将最长的公共子串应用于字符串及其反向。

LCS ("abcdefgedcg", "gcdegfedcba") = "cde"

编辑：不作为子potatoswatter指出，不子。

请参阅http://en.wikipedia.org/wiki/Longest_common_subsequence_problem – Potatoswatter 2010-03-19 04:53:46