use*_*392 68 algorithm palindrome
在花了大约6-8个小时试图消化Manacher的算法之后,我准备好了.但在此之前,这是最后一次在黑暗中拍摄:有人可以解释一下吗？我不关心代码.我希望有人解释算法.
这里似乎是其他人在解释算法时似乎喜欢的地方:http: //www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
我理解你为什么要把字符串转换成'#ab#'到#a#b#b#a#之后我就输了.例如,前面提到的网站的作者说该算法的关键部分是:
if P[ i' ] ? R – i,
then P[ i ] ? P[ i' ]
else P[ i ] ? P[ i' ]. (Which we have to expand past
the right edge (R) to find P[ i ])
这似乎是错误的,因为他/她在一点上说当P [i'] = 7并且P [i]不小于或等于R-i时P [i]等于5.
如果你不熟悉这个算法,这里有一些更多的链接:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html(我试过这个,但是术语很糟糕,令人困惑.首先,有些东西没有定义.还有太多的变量.你需要一个清单来回忆一下变量是指哪些变量.)
另一个是:http://www.akalin.cx/longest-palindrome-linear-time(祝你好运)
该算法的基本要点是在线性时间内找到最长的回文.它可以在O(n ^ 2)中以最小到中等的努力量完成.这个算法应该非常"聪明"才能将其降低到O(n).
Vau*_*ato 38
我同意在解释链接时逻辑不正确.我在下面提供一些细节.
Manacher的算法填写表P [i],其中包含以i为中心的回文延伸的范围.如果P [5] = 3,则位置5两侧的三个字符是回文的一部分.该算法利用了这样一个事实:如果你找到了一个很长的回文,你可以通过查看左侧P的值来快速填充回文右侧的P值,因为它们应该主要是相同.
我将首先解释你所谈论的案例,然后我会根据需要扩展这个答案.
R表示以C为中心的回文右侧的索引.这是您指示的地方的状态:
C=11
R=20
i=15
i'=7
P[i']=7
R-i=5
逻辑是这样的:
if P[i']<=R-i: // not true
else: // P[i] is at least 5, but may be greater
如果测试失败,则链接中的伪代码表示P [i]应该大于或等于P [i'],但我认为它应该大于或等于Ri,并且解释将其提高.
由于P [I"]比日时,在我为中心的回文"延伸过去在C.中心我们知道中心的回文回文在我至少会日字符宽,因为我们仍然具有对称性到这一点,但我们必须明确地搜索.
如果P [i']不大于Ri,则以i'为中心的最大回文位于以C为中心的最大回文范围内,因此我们知道P [i]不能大于P [i] "].如果是的话,我们就会有矛盾.这意味着我们能够将以i为中心的回文扩展到P [i']之外,但是如果可以的话,那么由于对称性,我们也能够将中心的回文延伸到i',但它已经是应该尽可能大.
此案例如前所述:
C=11
R=20
i=13
i'=9
P[i']=1
R-i=7
在这种情况下,P [i'] <= Ri.由于我们距离以C为中心的回文边缘仍有7个字符,因此我们知道i周围至少7个字符与i'周围的7个字符相同.由于i'周围只有一个字符回文,所以我周围也有一个字符回文.
j_random_hacker注意到逻辑应该更像这样:
if P[i']<R-i then
P[i]=P[i']
else if P[i']>R-i then
P[i]=R-i
else P[i]=R-i + expansion
如果P [i'] <Ri,那么我们知道P [i] == P [i'],因为我们仍然在以C为中心的回文范围内.
如果P [i']> Ri,那么我们知道P [i] == Ri,因为否则以C为中心的回文将延伸超过R.
因此,在P [i'] == Ri的特殊情况下,扩展实际上是必要的,因此我们不知道P [i]处的回文是否可能更长.
通过设置P [i] = min(P [i'],Ri)然后始终扩展,在实际代码中处理.这种方式不会增加时间复杂度,因为如果不需要扩展,则进行扩展所花费的时间是不变的.
Jac*_*ski 12
这个网站上的算法似乎可以理解 http://www.akalin.cx/longest-palindrome-linear-time
要理解这种特殊方法,最好的方法是尝试解决纸上问题并捕捉可以实施的技巧,以避免检查每个可能中心的回文.
首先回答你自己 - 当你找到给定长度的回文时,让我们说5 - 你不能作为下一步跳到这个回文结尾(跳过4个字母和4个中间字母)？
如果你试图创建一个长度为8的回文并放置另一个长度> 8的回文,其中心位于第一回文的右侧,你会发现一些有趣的东西.尝试一下:Palindrome长度为8 - WOWILIKEEKIL - 喜欢+ ekiL = 8现在在大多数情况下,您可以记下两个E作为中心之间的位置和数字8作为长度并跳过最后一个L之后寻找更大的回文的中心.
这种方法不正确,较大的回文中心可以在ekiL内部,如果你在最后一个L之后跳过,你就会错过它.
在找到LIKE + EKIL后,你将8放在这些算法使用的数组中,这看起来像:
[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]
对于
[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#]
诀窍在于你已经知道,8之后的下一个7(8-1)数字很可能与左侧相同,所以下一步是自动从8的左边到8的右边复制7个数字介意他们还没有最终决定.数组看起来像这样
[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3](我们在8)
对于
[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#,E,#,K,#,I,#,L]
让我们举个例子,这样的跳转会破坏我们当前的解决方案,看看我们能注意到什么.
WOWILIKEEKIL - 让我们尝试在EKIL内的某个地方制作更大的回文.但它不可能 - 我们需要将EKIL改为包含回文的东西.什么？OOOOOh - 这就是诀窍.在我们目前的回文的右侧,中心有一个更大的回文的唯一可能性是它已经在回文的右侧(和左侧).
让我们尝试基于WOWILIKEEKIL构建一个我们需要将EKIL更改为例如EKIK,将I作为更大回文的中心 - 记得将LIKE更改为KIKE.我们棘手的回文的首字母将是:
WOWIKIKEEKIK
如前所述 - 让最后一个我成为比KIKEEKIK更大的pallindrome的中心:
WOWIKIKEEKIKEEKIKIW
让我们把阵列变成我们旧的pallindrom,并找出如何利用其他信息.
对于
[_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W]
它将是[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8
我们知道下一个I - 3将是最长的pallindrome,但让我们忘记它了一下.让我们将数组中的数字从8的左边复制到右边(8个数字)
[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]
在我们的循环中,我们处于E与8号之间.对于我(未来中间最大的pallindrome),我们不能直接跳到K(当前最大的pallindrome的最后一个字母)有什么特别之处？特别之处在于它超出了阵列的当前大小......怎么样？如果你向3的右边移动3个空格 - 你就不在数组中了.这意味着它可以是最大的pallindrome的中间,你可以跳到最远的是这封信I.
对不起这个答案的长度 - 我想解释一下algorythm并且可以向你保证 - @OmnipotentEntity是对的 - 在向你解释后我明白了它更好:)
scv*_*scv 11
到目前为止,我已经在以下链接中找到了最好的解释之一:
http://tarokuriyama.com/projects/palindrome2.php
它还具有在问题中提到的第一个链接中使用的相同字符串示例(babcbabcbaccba)的可视化.
除了这个链接,我还找到了代码
http://algs4.cs.princeton.edu/53substring/Manacher.java.html
我希望对那些努力理解这个算法的症结的人有所帮助.
全文:http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/
首先,让我们仔细观察回文以找到一些有趣的属性.例如,S1 ="abaaba"和S2 ="abcba",两者都是回文,但它们之间的非平凡(即不是长度或字符)差异是什么？S1是以i = 2和i = 3(不存在的空间!)之间的不可见空间为中心的回文.另一方面,S2以i = 2(即c)的字符为中心.无论奇数/偶数长度如何,为了优雅地处理回文的中心,我们通过在字符之间插入特殊字符$来变换回文.那么S1 ="abba"并且S2 ="abcba"将被转换为T1 ="$ a $ b $ a $ a $ b $ a $",其中i = 6且T2 ="$ a $ b $ c $ b $ a $"以i = 5为中心.现在,我们可以看到中心存在且长度一致2*n + 1,其中n =原始字符串的长度.例如,
i' c i
-----------------------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
-----------------------------------------------------
T1=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
-----------------------------------------------------
接下来,从中心c周围的(变形的)回文T的对称性质观察,对于0 <= k <= c,T [ck] = T [c + k].那就是位置ck和c + k彼此镜像.让我们换一种说法,对于中心c右侧的索引i,镜像索引i'位于c的左侧,使得c-i'= ic => i'= 2*ci,反之亦然.那是,
对于回文子串中心c右侧的每个位置i,i的镜像位置是i'= 2*ci,反之亦然.
让我们定义一个数组P [0..2*n],使得P [i]等于以i为中心的回文长度.请注意,长度实际上是通过原始字符串中的字符数来衡量的(通过忽略特殊字符$).同样,min和max分别是以c为中心的回文子串的最左边界和最右边界.所以,min = cP [c]和max = c + P [c].例如,对于回文S ="abaaba",变换后的回文T,镜像中心c = 6,长度数组P [0..12],min = cP [c] = 6-6 = 0,max = c + P [c] = 6 + 6 = 12,两个样本镜像索引i和i'如下图所示.
min i' c i max
-----------------------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
-----------------------------------------------------
T=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
-----------------------------------------------------
P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
-----------------------------------------------------
使用这样的长度数组P,我们可以通过查看P的最大元素找到最长的回文子串的长度.即,
P [i]是在变换后的字符串T中以i为中心的回文子串的长度,即.以原始字符串S的i/2为中心; 因此,最长的回文子串将是从索引(i max -P [i max ])/ 2 开始的长度P [i max ] 的子串,使得i max是P中的最大元素的索引.
让我们在下面为我们的非回文示例字符串S ="babaabca"绘制一个类似的图.
min c max
|----------------|-----------------|
--------------------------------------------------------------------
idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
---------------------------------------------------------------------
T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
---------------------------------------------------------------------
P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
---------------------------------------------------------------------
问题是如何有效地计算P. 对称性质表明我们可能通过在左侧的镜像索引i'处使用先前计算的P [i']来计算P [i]的以下情况,因此跳过了大量计算.让我们假设我们有一个参考回文(第一回文)开始.
如果第二回文位于第一回文范围内,则第三回文的中心位于第一回文的右侧,其长度与第二回文的长度完全相同,如果第二回文位于第一回文的范围内,则第二回文位于第一回文的边界内.至少一个角色.例如,在下图中,第一个回文以c = 8为中心并以min = 4和max = 12为界,以i = 9为中心的第三回文长度(镜像索引i'= 2*ci = 7)是,P [i] = P [i'] = 1.这是因为以i'为中心的第二回文位于第一回文范围内.类似地,P [10] = P [6] = 0.
|----3rd----|
|----2nd----|
|-----------1st Palindrome---------|
min i' c i max
|------------|---|---|-------------|
--------------------------------------------------------------------
idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
---------------------------------------------------------------------
T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
---------------------------------------------------------------------
P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? |
---------------------------------------------------------------------
现在,问题是如何检查这种情况？注意,由于段[min..i']的对称属性长度等于段[i..max]的长度.另外,请注意,如果第2回文的左边缘位于第1回文的左边界内,则第2回文完全在第1回文范围内.那是,
i'-P[i'] >= min
=>P[i']-i' < -min (negate)
=>P[i'] < i'-min
=>P[i'] < max-i [(max-i)=(i'-min) due to symmetric property].
结合案例1中的所有事实,
P [i] = P [i'],iff(max-i)> P [i']
如果第二回文结构遇到或超出第一回文结构的左边界,则第三回文保证至少具有从其自身中心到第一回文结构的右最外侧字符的长度.该长度从第二回文的中心到第一回文的左最外面的字符是相同的.例如,在下图中,以i = 5为中心的第二回文延伸超出第一回文的左边界.所以,在这种情况下,我们不能说P [i] = P [i'].但是第三回文的长度以i = 11为中心,P [i]至少是从其中心i = 11到以c为中心的第一回文的右边界max = 12的长度.即,P [i]> = 1.这意味着,当且仅当下一个直接字符超过最大匹配与镜像字符完全匹配时,第三个回文可以延伸超过最大值,并且我们继续进行此检查.例如,在这种情况下P [13]!= P [9]并且它不能被扩展.所以,P [i] = 1.
|-------2nd palindrome------| |----3rd----|---?
|-----------1st Palindrome---------|
min i' c i max
|----|-----------|-----------|-----|
--------------------------------------------------------------------
idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
---------------------------------------------------------------------
T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
---------------------------------------------------------------------
P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? |
---------------------------------------------------------------------
那么,如何检查这种情况？这只是案例1的失败检查.也就是说,第二回文将延伸超过第一回文iff的左边缘,
i'-P[i'] < min
=>P[i']-i' >= -min [negate]
=>P[i'] >= i'-min
=>P[i'] >= max-i [(max-i)=(i'-min) due to symmetric property].
也就是说,P [i]至少是(max-i)iff(max-i)P [i]> =(max-i),iff(max-i)现在,如果第三回文确实延伸超过max那么我们需要更新新回文的中心和边界.
如果以i为中心的回文确实扩展到最大值,则我们有新的(扩展的)回文,因此在c = i处有一个新的中心.将max更新到新回文的最右边界.结合案例1和案例2中的所有事实,我们可以提出一个非常漂亮的小公式:
Case 1: P[i] = P[i'], iff (max-i) > P[i']
Case 2: P[i]>=(max-i), iff (max-i) = min(P[i'], max-i).
也就是说,当第三回文不能延伸超过最大值时,P [i] = min(P [i'],max-i).否则,我们在c = i的中心处有新的第三回文并且新的max = i + P [i].
第一和第二回文都没有提供信息来帮助确定第四回文的回文长度,第四回文的中心位于第一回文的右侧之外.也就是说,如果i> max,我们无法预先确定P [i].那是,
P [i] = 0,iff max-i <0结合所有案例,我们得出以下公式:
P [i] = max> i？min(P [i'],max-i):0.如果我们可以扩展到max以上,那么我们通过匹配超出max的字符与相对于c = i的新中心的镜像字符进行扩展.最后,当我们有不匹配时,我们更新新的max = i + P [i].
参考:维基页面中的算法描述