O(n)回文子串算法

1、O（n）回文子串算法    這里，我介紹一下O（n）回文串處理的一種方法。Manacher算法.原文地址：    其實(shí)原文說(shuō)得是比較清楚的，只是英文的，我這里寫(xiě)一份中文的吧。    首先：大家都知道什么叫回文串吧，這個(gè)算法要解決的就是一個(gè)字符串中最長(zhǎng)的回文子串有多長(zhǎng)。這個(gè)算法可以在O（n）的時(shí)間復(fù)雜度內(nèi)既線性時(shí)間復(fù)雜度的情況下，求出以每個(gè)字符為中心的最長(zhǎng)回文有多長(zhǎng)，    這個(gè)算法有一個(gè)很巧妙的地方，它把奇數(shù)的回文串和偶數(shù)的回文串統(tǒng)一起來(lái)考慮了。這一點(diǎn)一直是在做回文串問(wèn)題中時(shí)比較煩的地方。這個(gè)算法還有一個(gè)很好的地方

2、就是充分利用了字符匹配的特殊性，避免了大量不必要的重復(fù)匹配。    算法大致過(guò)程是這樣。先在每?jī)蓚€(gè)相鄰字符中間插入一個(gè)分隔符，當(dāng)然這個(gè)分隔符要在原串中沒(méi)有出現(xiàn)過(guò)。一般可以用#分隔。這樣就非常巧妙的將奇數(shù)長(zhǎng)度回文串與偶數(shù)長(zhǎng)度回文串統(tǒng)一起來(lái)考慮了（見(jiàn)下面的一個(gè)例子，回文串長(zhǎng)度全為奇數(shù)了），然后用一個(gè)輔助數(shù)組P記錄以每個(gè)字符為中心的最長(zhǎng)回文串的信息。Pid記錄的是以字符strid為中心的最長(zhǎng)回文串，當(dāng)以strid為第一個(gè)字符，這個(gè)最長(zhǎng)回文串向右延伸了Pid個(gè)字符。    原串：    w aa bwsw f d 

3、0;   新串：   # w # a # a # b # w # s # w # f # d #輔助數(shù)組P：  1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1    這里有一個(gè)很好的性質(zhì)，Pid-1就是該回文子串在原串中的長(zhǎng)度（包括#）。如果這里不是特別清楚，可以自己拿出紙來(lái)畫(huà)一畫(huà)，自己體會(huì)體會(huì)。當(dāng)然這里可能每個(gè)人寫(xiě)法不盡相同，不過(guò)我想大致思路應(yīng)該是一樣的吧。    好，我們繼續(xù)?，F(xiàn)在的關(guān)鍵問(wèn)題就在于怎么在O（n）時(shí)間復(fù)雜度內(nèi)求出P數(shù)組了。只要把這個(gè)P數(shù)組求出來(lái)，最長(zhǎng)回文子串就可以直接掃

4、一遍得出來(lái)了。    由于這個(gè)算法是線性從前往后掃的。那么當(dāng)我們準(zhǔn)備求Pi的時(shí)候，i以前的Pj我們是已經(jīng)得到了的。我們用mx記在i之前的回文串中，延伸至最右端的位置。同時(shí)用id這個(gè)變量記下取得這個(gè)最優(yōu)mx時(shí)的id值。（注：為了防止字符比較的時(shí)候越界，我在這個(gè)加了#的字符串之前還加了另一個(gè)特殊字符$，故我的新串下標(biāo)是從1開(kāi)始的）好，到這里，我們可以先貼一份代碼了。1. void pk( 2. 3.     int i; 4.     int mx = 0; 5.     int id; 6.    

5、; for(i=1; i 7.     8.         if( mx > i 9.             pi = MIN( p2*id-i, mx-i ;         10.         else 11.             pi = 1; 12.   

6、0;     for(; stri+pi = stri-pi; pi+ 13.              14.         if( pi + i > mx 15.          16.             mx = pi + i; 17.          &

7、#160;  id = i; 18.         19.     20.     代碼是不是很短啊，而且相當(dāng)好寫(xiě)。很方便吧，還記得我上面說(shuō)的這個(gè)算法避免了很多不必要的重復(fù)匹配吧。這是什么意思呢，其實(shí)這就是一句代碼。if( mx > i     pi = MIN( p2*id-i, mx-i ;就是當(dāng)前面比較的最遠(yuǎn)長(zhǎng)度mx>i的時(shí)候，Pi有一個(gè)最小值。這個(gè)算法的核心思想就在這里，為什么P數(shù)組滿足這樣一個(gè)性質(zhì)呢?   （下面的部分為圖片形式）    看完這個(gè)算法，你有可能會(huì)覺(jué)得這種算法在哪會(huì)用到呢？其實(shí)回文串后綴數(shù)組也可以做。只是復(fù)雜度是O（n log n）的，而且一般情況下也不會(huì)刻意去卡一個(gè)log n的算法?？烧胔du就有這么一題，你用后綴數(shù)組寫(xiě)怎么都得T（當(dāng)然應(yīng)該是