Strings #1 Application of KMP

Shortest Palindrome

Problem Statement: here

Solution: 

So this problem requires us to find the shortest length of palindrome by appending characters in front of the string. Clearly, the fewer characters we append, the shortest is the length. For this purpose, we must be interested in finding the longest palindromic prefix substring of the given string. This allows us to know the minimal characters from behind which when appended to the front will give us the shortest palindrome. 

For example string = "ABCCBADEA", we know the longest palindromic prefix is "ABCCBA" and if we append "AED", to the front, we will get the shortest palindrome.

So, how to find the longest prefix palindrome of a given string?

We will use the help of the KMP failure table to calculate the longest prefix palindrome for our string. We know that the failure table keeps track of the longest prefix which is also the suffix of the given string. Exploiting this fact, we can actually construct a new string T = S*S' where S' is the reverse string of S. Once we do this, let's say S = AB where A is a palindrome of largest size and B is rest, then T = AB*B'A, clearly we see KMP can be used to find out the A here.

The code:

class Solution { public: string shortestPalindrome(string s) { int n = s.size(); string sprime(s); reverse(sprime.begin(), sprime.end()); string stot = s + "*" + sprime; int ntot = stot.size(); vector<int> f(ntot,0); for (int i = 1; i < ntot; i++) { int t = f[i - 1]; while (t > 0 && stot[i] != stot[t]) t = f[t - 1]; if (stot[i] == stot[t]) ++t; f[i] = t; } return sprime.substr(0, n - f[ntot - 1]) + s; } };

What next after learning this application? 

Try your hands on this application here: https://codeforces.com/contest/1326/problem/D2
I will discuss it's solution by tomorrow!