spoj ➡ classical ➡ epalin ➡ Extend to Palindrome

you can get the problem statement from here.

we have to calculate length of longest palindromic suffix of given string and then concatenate the given string with the part other than the longest palindromic suffix.

As we already know how to generate longest Proper Prefix of string such that it is also it’s suffix (used in KMP algorithm), we have calculate the longest proper pefix of a new string NS.

NS = str(reversed(S)) + S

the longest proper prefix of NS which is also a suffix of NS is our palindromic suffix of S.

https://gist.github.com/eightnoteight/5425fe5ac09b3ce7c83c

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s