Solution:

We need to find the longest palindrome suffix of S.

- compute the Z function for reverse(S)$S
- find the smallest i<n such that i+Z[i] = n
- append reverse(S[1,…,i-1]) to the end of S.

Advertisements

Leave a reply

Solution:

We need to find the longest palindrome suffix of S.

- compute the Z function for reverse(S)$S
- find the smallest i<n such that i+Z[i] = n
- append reverse(S[1,…,i-1]) to the end of S.

Advertisements

Solution:

- compute KMP function f for the input string
- for each i<n, if and print with

The hardest thing here is to prove that this procedure is correct.