开发者

How to find the longest continuous subsequence whose reverse is also a subsequence

开发者 https://www.devze.com 2022-12-23 04:44 出处:网络
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.

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 开发者_StackOverflow中文版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.


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.

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

EDIT: not subsequence as potatoswatter points out, not subsequence.

0

精彩评论

暂无评论...
验证码 换一张
取 消