Substring and its reverse in a string

My professor was talking about this in a Dynamic programming class and asked us to think over it. She gave us some examples as well. Given a string, we were to find the longest continuous subseque开发者_如何学Cnce whose reverse is also a subsequence present in the given string.

Example:

INPUT: pqrstuvtsrv
OUTPUT: i=3, k=2

rst -> tsr (rst found first at i=3 and for 2 more positions)

INPUT: mpqrsrqp
OUTPUT: i=2, k=6
pqrsrqp in reverse

INPUT: mmpqssss
OUTPUT: i=5, k=3

I thought of putting the string and its reverse into 2 different arrays and comparing character by character. But I'm sure this is not the best way to do it. Any suggestions as to what could be the most efficient ?

This is a variation on the Longest common substring problem. You are looking for the longest common substring of your input and its reverse.

There may be a simpler solution for this specific case, but for the moment, I doubt it. =)

This doesn't work because you also have to watch for overlap. If you use LCS, you'll find palindromes as well, which may or may not have their reverse in the original string.

Sounds like a job for a suffix tree (actually, two, or a generalized suffix tree for both of them). But this being a dynamic programming class, not a data structures class, maybe not.

If you want a complete spoiler, search for "longest common substring problem". But I'd advise you to avoid looking too closely at anything that appears to be a solution. One of the problems with hints for dynamic programming problems is that often the solution rests on one single very clever observation, and you either get it or you don't.

What you are looking for is named Longest palindromic substring and it has known linear time solutions. Hope I helped.