Substring and its reverse in a string

Question

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 subsequence 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 ?

Answer 1

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. =)

Answer 2

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.