Given a string

First insert a special character ‘#’ between each pair of adjacent characters of

Let

Assume

Is it the algorithm linear time? The answer is yes.

First the overall number of unsuccessful comparisons is obviously at most

A more careful analysis show that

So the number of overall comparisons is a most

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

*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])}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

on January 7, 2011 at 1:07 am |paul1987@stone: hi, can you please clarify what ‘a’ is in P[a] ?

Thanks

paul

on January 7, 2011 at 9:33 am |stonea=argmax{ P[j]+j | j<i }

on May 9, 2011 at 3:57 pm |LBHi,

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 |stoneHi,

Here is a simple example, for string “a#b#a#a#b#a”. Hope it will help you.

At position #0: P[0]=0, the longest palindrome is “a”.

At position #1: max of {P[0]+0} is 0, so we just check the “a#b” to determine P[1]. It turns out that P[1]=0

At position #2: max of { P[0]+0, P[1]+1} is P[1]+1=1, so we just check “#b#”,”a#b#a” to determine P[1]. It turns out that P[2]=2.

At position #3: max of { P[0]+0,P[1]+1,P[2]+2} is P[2]+2=4. We can know that p[3]>=Min{ P[2*2-3], 2*2-3-(2-P[2]) } = 0, so we check “b#a” to determine that P[3]=0

At position #4: max of { P[0]+0,P[1]+1,P[2]+2,P[3]+3} is P[2]+2=4. So P[4]>=Min{ P[2*2-4], 2*2-4-(2-P[2]) } = 0, we check “#a#” to determine that P[4]=1

At postion #5: max of { P[0]+0,P[1]+1,P[2]+2,P[3]+3, P[4]+4} is P[4]+4=5, so P[5]>=Min{P[2*4-5], 2*4-5-(4-P[4]) }=0, we check “a#a”,…,”a#b#a#a#b#a” to determine that P[5]=5.

At position #6: max of {P[0]+0,P[1]+1,P[2]+2,P[3]+3, P[4]+4, P[5]+5} is P[5]+5=10, so P[6]>=Min{ P[2*5-6], 2*5-6-(5-P[5])} =1, we check “a#a#b” to determine that P[6]=1. (here we don’t need to check “#a#”)

At position #7: max of {P[0]+0,P[1]+1,P[2]+2,P[3]+3, P[4]+4, P[5]+5,P[6]+6} is P[5]+5=10, so P[7]>=Min{ P[2*5-7], 2*5-7-(5-P[5]) }=0, we check “a#b” to determine that P[7]=0.

At position #8: max of {P[0]+0,P[1]+1,P[2]+2,P[3]+3, P[4]+4, P[5]+5,P[6]+6,…} is P[5]+5=10, so P[8]>=Min{ P[2*5-8], 2*5-8-(5-P[5])} =2,

we don’t need check any substring due to the boundary.

……

on May 31, 2011 at 1:10 pm |SG ...I am still confused …

how you come to this conclusion ::

Assume P[a]+a=max{ P[j]+j : j

= i, then we haveP[i] >= min{ P[2*a-i], 2*a-i-(a- P[a])}.

on October 15, 2011 at 7:28 pm |USACO section 1.3 Calf Flac | ☆零☆ || coderling[…] 原文地址： https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-pali… 其实原文说得是比较清楚的，只是英文的，我这里写一份中文的吧。 […]

on November 6, 2011 at 7:55 pm |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

on November 21, 2011 at 3:08 pm |Longest Palindromic Substring Part II | LeetCode[…] 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 […]

on December 4, 2012 at 5:20 pm |Longest Palindromic Substring(最长回文子串)的O(n)解法 | Feel LuckyFeel Lucky[…] http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=140283 https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-pali… http://www.geeksforgeeks.org/archives/19155 所以自己总接一下备忘。简单描述： […]

on May 19, 2014 at 2:39 pm |LeetCode: Longest Palindromic Substring | billyinn[…] The algorithm is called Manacher Algorithm. You can find more details about the algorithm in this page […]

on September 18, 2014 at 7:44 am |shuliyeyyou are a legend :D, can’t find a better explanation than this one.

on September 18, 2014 at 3:41 pm |leetcode example | Multimedia Feedback Demo[…] (Best explanation if you can □□□□ Chinese) » A simple linear □□□□ algorithm for finding longest palindrome sub-string » Finding Palindromes » Finding the □□□□□□□ […]

on December 26, 2014 at 1:11 pm |Manacher’s ALGORITHM: O(n) algorithm for Longest Palindromic Substring | 常夏[…] http://www.felix021.com/blog/page.php?pageid=6 http://blog.csdn.net/ggggiqnypgjg/article/details/6645824 https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-pali… […]

on January 3, 2015 at 10:45 am |Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串 | Peoce's Bolg[…] 源于这两篇文章： http://blog.csdn.net/ggggiqnypgjg/article/details/6645824 https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-pali… […]

on April 26, 2016 at 10:29 pm |POJ 3974 最长回文字串 Manacher算法 – Weymire's Blog[…] 题目链接：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 […]

on June 22, 2017 at 1:28 am |Manacher 算法 – PhoenixGS[…] https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-pal… […]