Feeds:
Posts
Comments

## A simple linear time algorithm for finding longest palindrome sub-string

Given a string S, we are to find the longest sub-string s of S such that the reverse of s is exactly the same as s.
First insert a special character ‘#’ between each pair of adjacent characters of S, in front of S and at the back of S. After that, we only need to check palindrome sub-strings of odd length.
Let P[i] be the largest integer d such that S[i-d,…,i+d] is a palindrome.  We calculate all P[i]s from left to right. When calculating P[i], we have to compare S[i+1] with S[i-1], S[i+2] with S[i-2] and so on. A comparison is successful if two characters are the same, otherwise it is unsuccessful. In fact, we can possibly skip some unnecessary comparisons utilizing the previously calculated P[i]s.
Assume P[a]+a=max{ P[j]+j :  j<i }. If P[a]+a >= i, then we have
P[i] >= min{ P[2*a-i],  2*a-i-(a- P[a])}
.
Is it the algorithm linear time? The answer is yes.
First the overall number of unsuccessful comparisons is obviously at most N.
A more careful analysis show that S[i] would never be compared successfully with any S[j](j<i) after its first time successful comparison with some S[k] (k<i).
So the number of overall comparisons is a most 2N

It turns out that this algorithm is called Manacher’s algorithm.
Advertisements

### 16 Responses

1. on January 7, 2011 at 1:07 am | Reply paul1987

@stone: hi, can you please clarify what ‘a’ is in P[a] ?
Thanks
paul

• on January 7, 2011 at 9:33 am | Reply stone

a=argmax{ P[j]+j | j<i }

2. on May 9, 2011 at 3:57 pm | Reply LB

Hi,

Your article seems quite interesting. Would you mind to explain this idea a bit with a trivial example? I tried hours to comprehend your recurrence to compute the longest palindromic substring; but failed 😦

So, your help would be highly appreciated. Thanks.

-Josh

• on May 10, 2011 at 10:58 am | Reply stone

Hi,
Here is a simple example, for string “a#b#a#a#b#a”. Hope it will help you.
At position #0: P=0, the longest palindrome is “a”.
At position #1: max of {P+0} is 0, so we just check the “a#b” to determine P. It turns out that P=0
At position #2: max of { P+0, P+1} is P+1=1, so we just check “#b#”,”a#b#a” to determine P. It turns out that P=2.
At position #3: max of { P+0,P+1,P+2} is P+2=4. We can know that p>=Min{ P[2*2-3], 2*2-3-(2-P) } = 0, so we check “b#a” to determine that P=0
At position #4: max of { P+0,P+1,P+2,P+3} is P+2=4. So P>=Min{ P[2*2-4], 2*2-4-(2-P) } = 0, we check “#a#” to determine that P=1
At postion #5: max of { P+0,P+1,P+2,P+3, P+4} is P+4=5, so P>=Min{P[2*4-5], 2*4-5-(4-P) }=0, we check “a#a”,…,”a#b#a#a#b#a” to determine that P=5.
At position #6: max of {P+0,P+1,P+2,P+3, P+4, P+5} is P+5=10, so P>=Min{ P[2*5-6], 2*5-6-(5-P)} =1, we check “a#a#b” to determine that P=1. (here we don’t need to check “#a#”)
At position #7: max of {P+0,P+1,P+2,P+3, P+4, P+5,P+6} is P+5=10, so P>=Min{ P[2*5-7], 2*5-7-(5-P) }=0, we check “a#b” to determine that P=0.
At position #8: max of {P+0,P+1,P+2,P+3, P+4, P+5,P+6,…} is P+5=10, so P>=Min{ P[2*5-8], 2*5-8-(5-P)} =2,
we don’t need check any substring due to the boundary.
……

3. on May 31, 2011 at 1:10 pm | Reply SG ...

I am still confused …

how you come to this conclusion ::
Assume P[a]+a=max{ P[j]+j : j= i, then we have
P[i] >= min{ P[2*a-i], 2*a-i-(a- P[a])}.

4. […] 原文地址： https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-pali… 其实原文说得是比较清楚的，只是英文的，我这里写一份中文的吧。 […]

5. on November 6, 2011 at 7:55 pm | Reply monish001

@stone: 1.should NOT the string be “#a#b#a#a#b#a#” instead of “a#b#a#a#b#a”?
2. also doubt asked by SG

Thanks

6. […] O(N) 时间求字符串的最长回文子串 (Best explanation if you can read Chinese) » A simple linear time algorithm for finding longest palindrome sub-string » Finding Palindromes » Finding the Longest Palindromic Substring in Linear Time […]

7. […] The algorithm is called Manacher Algorithm. You can find more details about the algorithm in this page […]

8. on September 18, 2014 at 7:44 am | Reply shuliyey

you are a legend :D, can’t find a better explanation than this one.

9. […] (Best explanation if you can □□□□ Chinese) » A simple linear □□□□ algorithm for finding longest palindrome sub-string » Finding Palindromes » Finding the □□□□□□□ […]

10. […] 题目链接：http://poj.org/problem?id=3974 在这里我不打算详细介绍Manacher算法，因为网上有太多太多的启蒙教程。只是提出两个最关键的点来加深理解： 关于Manacher算法的两个核心思想： 1. 通过在原字符串中插入特殊字符的方式将其长度变为奇数。 2. 利用对称性压缩计算，达到线性时间复杂度。 比如原本的字符串是xabbba5，那么可以将这个字符串转化成#x#a#b#b#b#a#5#，然后处理这个新的字符串。 然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度，计算过程和对对称性的利用请参考 华山大师兄 的这篇博文： http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html 讲得非常透彻，图文并茂。 如何严格证明Manacher算法是线性时间复杂度的，可以在下面的这篇博客中了解： A simple linear time algorithm for finding longest palindrome sub-string […]