求回文子串O(n)manacher算法

1、求回文子串 0(n) manacher 算法回文串定義："回文串”是一個(gè)正讀和反讀都一樣的字符串，比如"level ”或者"noon ”等等就是回文串?；匚淖哟櫭剂x，即字符串中滿足回文性質(zhì)的子串。經(jīng)常有一些題目圍繞回文子串進(jìn)行討論，比如HDOJ_3068_最長(zhǎng)回文，求最長(zhǎng)回文子串的長(zhǎng)度。樸素算法是依次以每一個(gè)字符為中心向兩側(cè)進(jìn)行擴(kuò)展，顯然這個(gè)復(fù)雜度是 O(N2)的，關(guān)于字符串的題目常用的算法有KMP、后綴數(shù)組、AC自動(dòng)機(jī)，這道題目利用擴(kuò)展 KMP可以解答，其時(shí)間復(fù)雜度也很快O(N*logN)。但是，今天筆者介紹一個(gè)專門針對(duì)回文子串的算法，其時(shí)間復(fù)雜度為O(n

2、)，這就是manacher算法。大家都知道，求回文串時(shí)需要判斷其奇偶性，也就是求aba和abba的算法略有差距。然而，這個(gè)算法做了一個(gè)簡(jiǎn)單的處理，很巧妙地把奇數(shù)長(zhǎng)度回文串與偶數(shù)長(zhǎng)度回文串統(tǒng)一考慮，也就是在每個(gè)相鄰的字符之間插入一個(gè)分隔符，串的首尾也要加，當(dāng)然這個(gè)分隔符不能再原串中出現(xiàn)，一般可以用# '或者$'等字符。例如：原串：abaab新串：#a#b#a#a#b#這樣一來(lái)，原來(lái)的奇數(shù)長(zhǎng)度回文串還是奇數(shù)長(zhǎng)度，偶數(shù)長(zhǎng)度的也變成以# '為中心的奇數(shù)回文串了。接下來(lái)就是算法的中心思想，用一個(gè)輔助數(shù)組P記錄以每個(gè)字符為中心的最長(zhǎng)回文半徑，也就是Pi記錄以Stri字符為中心的最長(zhǎng)

3、回文串半徑。Pi最小為1,此時(shí)回文串為Stri 本身。新串： #a#b#a#a#b#P:12141252121我們可以證明Pi-1就是以Stri為中心的回文串在原串當(dāng)中的長(zhǎng)度。證明：1、顯然L=2*Pi-1 即為新串中以Stri為中心最長(zhǎng)回文串長(zhǎng)度。2、 以Stri為中心的回文串一定是以 #開頭和結(jié)尾的，例如“ #b#b# ”或“#b#a#b# ” 所以L減去最前或者最后的 # '字符就是原串中長(zhǎng)度的二倍，即原串長(zhǎng)度為 （L-1）/2，化簡(jiǎn) 的Pi-1。得證。依次從前往后求得P數(shù)組就可以了，這里用到了DP（動(dòng)態(tài)規(guī)劃）的思想，也就是求Pi的時(shí)候，前面的P值已經(jīng)得到了，我們利用回文串的特殊

4、性質(zhì)可以進(jìn)行一個(gè)大大的優(yōu)化。我先把核心代碼貼上：for (i= 1 ;i<n ;i+)if (MaxId>i)pi=Mi n(p2*id-i,MaxId-i);elsepi=1 ;while (ai+pi=：=ai-pi)pi+;if (pi+i>MaxId)Maxld=pi+i;id=i;retur na<b?a:b;殊字符，令P0= $ '最后位置默認(rèn)為 0 '不需要特殊處理。此外，我們用Maxld變量記錄在求i之前的回文串中，延伸至最右端的位置，同時(shí)用 id記錄取這個(gè) Maxld的id值。通過(guò)下面這句話，算法避免了很多沒必要的重復(fù)匹配。if (Ma

5、xld>i)pi=Mi n(p2*id-i,Maxld-i);那么這句話是怎么得來(lái)的呢，其實(shí)就是利用了回文串的對(duì)稱性，如下圖,idi Maxldretur na<b?a:b;retur na<b?a:b;j=2*id-i即為i關(guān)于id的對(duì)稱點(diǎn)，根據(jù)對(duì)稱性，Pj的回文串也是可以對(duì)稱到i這邊的，但是如果Pj的回文串對(duì)稱過(guò)來(lái)以后超過(guò)Maxld的話，超出部分就不能對(duì)稱過(guò)來(lái)了，如下圖，所以這里Pi為的下限為兩者中的較小者，pi=Min(p2*id-i,Maxld-i)。i Maxld算法的有效比較次數(shù)為Maxld次，所以說(shuō)這個(gè)算法的時(shí)間復(fù)雜度為0(n)。附HDOJ 3068 最長(zhǎng)回文

6、代碼:#i nclude <stdio.h>#defi ne M 110010char bM,aM<<1;intintpM<< 1 ;Min( int a, intb)1intmai n()int i,n ,id,MaxL,Maxld; while (scanf( "%s" ，&b1)!=EOF)MaxL=MaxId=0;for (i= 1 ;bi!='0'i+)a(i<<1 )=bi;a(i<<1)+ 1 = '#'a0='?'a 1= '#'n=(i<<1)+ 2;a n=0;Maxld=MaxL= 0;for (i= 1 ;i<n;i+)if (MaxId>i) Ipi=Mi n(p2*id-i,Maxld-i);elsepi=1 ;while (ai+pi=ai-pi)pi