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

2
votes

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.

2
c#calgorithmsequence
I get i=2 k=3 for the first example and i=5 k=4 for the second. - Potatoswatter
@Potatoswatter: No, you don't. Read the statement of the problem again. The definition of "k" is messed up. k is the length of the substring minus one, i is the one-based index. You are assuming that k is the length of the substring and i is the distance from the beginning, but that's not how they were defined. - Eric Lippert
@Eric: OK then. Although that works because he's guaranteed to find a substring for any non-empty input, still recommend to OP that he use normal programming conventions. - Potatoswatter
durp? stackoverflow.com/questions/2463364/… - BlueRaja - Danny Pflughoeft

2 Answers

5
votes

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

2
votes

apply longest common substring to the string and its reverse.

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

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