Minimum number of characters to be inserted at the end of a string to make it a palindrome

Question

The question is like this--

We have to find the minimum number of characters to be inserted at the end of a string to make it a palindrome.

So, in my efforts to do this problem, I figured that this is equivalent to finding the largest palindromic substring which is also a suffix of the string.

I could do this in O(n^2) easily but I am looking for a O(n) solution which is probably possible using modified KMP. Somebody please help me figure out.

Answer 1

I have an approach that uses hashing posted as an answer here.

You can indeed also use KMP. You can compute the prefix function for the reversed string, and then iterate your initial string from left to right:

KMP computes a function prefix[i] = longest prefix of the string that is a suffix of string[1..i]

However, we want to know the longest suffix of our string that is a prefix of the reversed string. Why? If we have:

15232 => reverse = 23251

Then the longest suffix of the string that is a prefix of the reversed string is 232. This is a palindrome, and it lets us find what you're asking because a suffix of the string overlaps a prefix of the reversed string if the two are palindromes.

You have the cases:

prefix[i] = length - i => you can get a palindrome of 
            length 2*prefix[i] centered at i and i+1

prefix[i] = length - i + 1 => you can get a palindrome of
            length 2*prefix[i] - 1 centered at i

prefix[i] < length - i => you can't have a palindrome, ignore this position

So it suffices to compute the prefix function of the KMP algorithm.