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

Question

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

例如:- 考虑序列:

abcdefgedcg这里 i=3 和 k=2

aabcdddd 这里 i=5, k=3

我试着查看原始最长公共(public)子序列问题，但那是用来比较两个序列以找到最长公共(public)子序列....但这里只有一个序列，我们必须从中找到子序列。请让我知道解决此问题的最佳方法是什么，以找到最佳解决方案。

Answer 1

实际上这是应用于序列及其反向的最长常见子字符串问题:http://en.wikipedia.org/wiki/Longest_common_substring_problem

这与最长公共(public)子序列不同:http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence