如何找到最长的连续子序列，其逆序也是子序列
假设我有一个序列x1,x2,x3.....xn，我想找到最长的连续子序列xi,xi+1,xi+2......xi+k，其逆序也是一个给定序列的子序列。 如果有多个这样的子序列，那么我还必须找到最小的 i。
例如：- 考虑序列：
abcdefgedcg 这里 i=3 和 k=2
aabcddddd 这里 i=5, k=3
我尝试查看原始的最长公共子序列问题，但它用于比较两个序列以找到最长公共子序列....但这里只有一个我们必须从中找到的序列的子序列。请让我知道解决这个问题的最佳方法是什么，以找到最佳解决方案。
Suppose I have a sequence x1,x2,x3.....xn, and I want to find the longest continuous subsequence xi,xi+1,xi+2......xi+k, whose reverse is also a subsequence of the given sequence.
And if there are multiple such subsequences, then I also have to find the smallest i.
ex:- consider the sequences:
abcdefgedcg
here i=3 and k=2
aabcdddd
here i=5, k=3
I tried looking at the original longest common subsequence problem, but that is used to compare the two sequences to find the longest common subsequence.... but here is only one sequence from which we have to find the subsequences. Please let me know what is the best way to approach this problem, to find the optimal solution.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
实际上，这是应用于序列及其反向的最长常见子字符串问题：http ://en.wikipedia.org/wiki/Longest_common_substring_problem
这与最长公共子序列不同：http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence
Actually this is the longest common substring problem applied to the sequence and its reverse: http://en.wikipedia.org/wiki/Longest_common_substring_problem
This is distinct from longest common subsequence: http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence
将最长公共子串应用于字符串及其反向。
编辑：不是马铃薯瓦特指出的子序列，不是子序列。
apply longest common substring to the string and its reverse.
EDIT: not subsequence as potatoswatter points out, not subsequence.