Substring and its reverse in a string
- by christa
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 ?
