Pages

Tuesday, November 23, 2010

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 Sk. With KMP, we can compute a table pi for S, where pi[k] is the length of the longest suffix of Sk, that is also a prefix of Sk. 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 Sk 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, SL 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


7 comments:

  1. Pura ta pori nai.. but valo lagce apnar ai blog er jonno. Exam ses hole porbo sob insallah. :) Carry on via. May Allah help you

    ReplyDelete
  2. About the part for the longest palindrome that is prefix, what to you get for the word BBAB.

    BBABBABB

    h[8] = 5 => L = 4, but this is not true

    ReplyDelete
  3. Andreja - h[8] = 5 => L = 5 (not 4) and initial size of string is 4, so you need to run to next: h[5] = 2 => L=2, h[2] = 1 => L = 1.
    If you are searching the longest prefix that is also palindrome, the answer will be 2 (the answer will be also 5, but this is for concatenated string, but not our original string)

    ReplyDelete
  4. To make myself clear:
    1. T = Y + reverse(Y);
    2. Compute pi[] for T;
    3. L = max (pi[]);
    4. While (L > n) L = pi[L];
    5. Return L;

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. your algorithm seems to be failed in the following case: "aabba" because of KMP table's characteristics. U can take a look at my discussion: http://traceformula.blogspot.com/2015/06/shortest-palindrome-and-kmp-algorithm.html

    ReplyDelete