Home | About | Apps | Github | Rss

Longest palindromic substring

The simplest naive solution, of looping through each character as the centre of palindrome, to finding longest palindromic substring, in a string, has O(n^2) time complexity. This can be improved to be solvable in linear time or O(N) complexity - and there are many ways to do it - one being creating a suffix tree of all prefixes and another being Manachers algorithm.

Manacher’s algorithm works pretty much the same way naive solution works, except, it tries to use the properties of palindromes i.e reflection around a centre to its advantage. After a long time trying to understand this algorithm, I managed to implement it.

Here is a simple solution in python

"""Manacher's algorithm implementation in python"""
import sys
# convert the string to have odd number of characters
# by inserting a token char between every character of the string
s = ("matata")
ps = ['#']
for c in list(s):
	ps.append(c)
	ps.append('#')
# ata -> becoms -> #a#t#a#
print ps
P = [0] * len(ps)
center = 0
right = 0
for i in range(len(ps)):
	mirror = 2 * center - 1;
	# the P[i] should be what its reflection is
	# or in case there is a mismatch in the initial set
	# it should be distance to right edge of known palindromes
	if i < right :
		P[i] = min( P[mirror], right - i )
	# attempt to expand palindrome at the center i
	# use previous computation
	while( (i+1+P[i])<len(ps) and ps[ i+ (1+P[i]) ] == ps[ i-(1+P[i]) ] ):
		P[i] += 1
	# now move the right edge of known palindromes
	# if P[i]+i is greater than known right edge
	if i+P[i] > right:
		center = i
		right = i + P[1]
# P simply contains the maximum length of all palindromes at each center
# Figuring out the actual string is a trivial problem
# so I leave thee here
print P

Test run

pogobook(20:36):python $ python manacher.py
['#', 'm', '#', 'a', '#', 't', '#', 'a', '#', 't', '#', 'a', '#']
[0, 1, 0, 1, 0, 3, 0, 5, 0, 3, 0, 1, 0]

More posts