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

Question

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.

Answer 1

apply longest common substring to the string and its reverse.

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

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

Answer 2

Actually this is the longest common sub*string* problem applied to the sequence and its reverse: http://en.wikipedia.org/wiki/Longest_common_substring_problem

This is distinct from longest common sub*sequence*: http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence