One Solution of the Palindromic-Prefix Problem

This is a follow-up of my last post titled "A Sub-Problem, A funny bug". On that post I wrote about a problem and stated the fact that, I had an idea of a solution using some alien algorithm called Z-algorithm and also about my failed attempt to solve it using the more familiar KMP algorithm.

But (happily :D) I did solve it using KMP. The solution is simple and beautiful (ah well... everyone thinks like this after solving an interesting problem :P)!

For convenience, I will state the problem again:
Given a string S of length n. Calculate a boolean array P in O(n) time, where P[k] = true, if the k-length prefix of S is a palindrome, and false otherwise.

Lets recall what the KMP algorithm does. Basically it's a fast algorithm for searching for a given pattern in some text in O(text.length) time with O(pattern.length) preprocessing time.

The preprocessing part is the one, that will provide us the trick to solve this problem. Lets denote the given string as S and it's k-length prefix as S_k. With KMP, we can compute a table pi for S, where pi[k] is the length of the longest suffix of S_k, that is also a prefix of S_k. Note that, here a string is not considered a suffix of itself.

To solve this problem, at first I solved a related question which is, How to find in linear time, what is the length of the longest palindromic prefix of S.

For this, the following observation helped me: If S is a palindrome and also is S_k for some k < S.length, then it's k-length suffix will also be a palindrome and vice verse. But, S will not necessarily be a palindrome.

Here comes the trick! We can, create a new string T = S+reverse_of(S). We shall compute the pi[] (also, know as the prefix function) for T.

Now that, T is a palindrome, min(S.length,pi[2*length]) will the length of the longest palindromic-prefix of S. Lets call this value L. As, S_L is a palindrome, P[L] will be the length of the next longest palindromic prefix and so on..

For example, consider the string:
S = "abacabax".
So, T = "abacabaxxabacaba".

For T, we get these pi[ ] values,
pi[1] = 0
pi[2] = 0
pi[3] = 1
pi[4] = 0
pi[5] = 1
pi[6] = 2
pi[7] = 3
pi[8] = 0
pi[9] = 0
pi[10] = 1
pi[11] = 2
pi[12] = 3
pi[13] = 4
pi[14] = 5
pi[15] = 6
pi[16] = 7 [ this is the value of L ]

Now, we can set,
P[7] = true,
next value for L = 3,[ because, pi[7] = 3 ]
so, we set,
P[3] = true,
next value for L = 1, [ pi[3] = 1 ]
so, we set,
P[1] = true,
next value for L = 0, [ pi[1] = 0 ]
P[0] = true, [ empty string is also a palindrome ]

rest of the indices of P will be set to false.

and we are done!

both the computation of pi and P takes time linear in terms of the length of S. So, we have solved our problem in linear time.

Here is the code that calculates the P[ ] array.

void calc_P(char S[])
{
 int len = strlen(S);

 // append reverse_of(S) with S itself
 for(int i = len-1, j = len; i >= 0; --i, ++j)
 {
     S[j] = S[i];
 } 

 // KMP pre-processing Begins
 pi[0] = -1; // pi[0] is undefined

 for(int i = 0; i < len*2; ++i)
 {
     int k = pi[i];
  
     while(k >= 0 && S[k]!=S[i])
     k = pi[k];
  
     pi[i+1] = k+1;
 }
 // KMP pre-processing Ends
  
 int L = min(len,pi[len*2]); // length of the longest palindrome-prefix

 memset(P,false,sizeof(P)); // set all P[k] to false

 while(L >= 0)
 {
     P[L] = true;
     L = pi[L];
 }
}

I guess I would write on the second way to solve this problem (yeah, that Z-algorithm thing!) because, I need to understand the fairly easy Z-algorithm in depth! :P

Practice Problem (also the parent problem of this sub-problem):
http://www.codeforces.com/contest/7/problem/D


...and, this blog is always inspired by: http://one-problem-a-day.blogspot.com