I think the question for some day, but I can`t solve....

please give hint.....

Edited by author 26.08.2008 05:22

First you can calculate prefix array for reversed word. And then run algorithm that finds occurence or reversed word in S1, but stop it when forward and backard iterators meet each other. Ignore requirement S2 to be nonempty for now, and take it into account when algorithm will be almost ready

Consider A - original string, B - reversed.
Build preffix array for B, run KMP (search for B in A) with slight fix. In usual KMP you find a number of letters, that coincide in strings, and want it to be equal to size of B. In this problem you just remember this number (let it be Q). So after KMP you know, that last Q letters are a palindrome.

The only moment is what needs to be done, if Q == size of A. Then you should undo last KMP step (Q = P[Q-1]) and find previous palindrome.