Seems like I may be the only person to have used a bioinformatics approach to the first problem! bl2seq to the rescue!! I'll explain my approach if anyone seems

Seems like I may be the only person to have used a bioinformatics approach to the first problem! bl2seq to the rescue!! I'll explain my approach if anyone seems interested... as I am not sure if posting solutions is acceptable here. Edit: As others seem to be posting gist/snips etc. so I guess it is OK. Step 0 - Copied parent string to file: p1.txt Step 1 - Used python to reverse the entire string and copy to second file: cat p1.txt | python -c "print raw_input()[::-1]" > p2.txt Step 2 - Formatted the two files, so as to be parsed as FASTA, by adding sequence name headers. Step 3 - Use bl2seq (blastp) locally or online to align the two "sequences". Final alignment shows only one major chunk of identity, i.e. the answer. So, in essence, a dynamic programming algo would work.