1
$\begingroup$

I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word.

I've seen this algorithm used for determining if a word is rotation of the other for example. We can concatenate first word with itself and look for a pattern which would be the second word (and if found, the answer is yes). But I cannot imagine how could I use KMP for my problem. I am not sure what would the pattern be etc. Can it also be done in linear time using KMP? Thank you.

$\endgroup$
  • $\begingroup$ Concatenate with its own reverse. $\endgroup$ – Dmitri Urbanowicz Oct 15 '18 at 11:43
  • $\begingroup$ @Dmitri Urbanowicz And what then? What would the search pattern be, if any? Or should I look how the prefix function looks in this concatenated string? Because I am not sure what would indicate the longest palindromic prefix now. $\endgroup$ – ThePopa611 Oct 15 '18 at 14:56
1
$\begingroup$

KMP algorithm is able to solve your problem. Suppose your input string can be represented as $S=AB$ where $A$ is a palindrome ($B$ can be an empty string). Now reverse $S$ we can get $S'=B'A$. consider the string $T=S*S'=AB*B'A$ where '*' is a character which doesn't appear in $S$.

As we can see, $A$ is a border of $T$. Conversely, if $X$ is a border of $T$, then $X$ is a palindrome and thus a palindromic prefix of $S$. So the answer of your problem is the longest border of $T$, which directly corresponds to the last item of "fail" array in KMP algorithm.

In fact, in order to obtain the longest palindromic prefix of a word, you can use some general methods such as Manacher's algorithm, which is the best choice in dealing palindromes.

Manacher's algorithm can find the longest palindromic substring for every palindromic center in linear time. For example, if the input string is "abbabbba", then the algorithm can give you the following results (every digit corresponds to a length of palindromic substring centered in its position):

a b b a b b b a  
101410501252101

Manacher's algorithm can solve your problem easily. After getting the longest palindromic substring for every palindromic center, you can simply check for every palindromic center, whether the longest palindromic substring touches the left first character. Consequently, the whole algorithm can be done in $O(|s|)$, where $s$ is the input string.

$\endgroup$
  • $\begingroup$ Oh, I did not think of the character which does not belong to the string. Now I get it. Thanks. $\endgroup$ – ThePopa611 Oct 15 '18 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.