O(n)回文子串算法

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

2、就是充分利用了字符匹配的特殊性，避免了大量不必要的重復(fù)匹配。    算法大致過程是這樣。先在每兩個相鄰字符中間插入一個分隔符，當(dāng)然這個分隔符要在原串中沒有出現(xiàn)過。一般可以用#分隔。這樣就非常巧妙的將奇數(shù)長度回文串與偶數(shù)長度回文串統(tǒng)一起來考慮了（見下面的一個例子，回文串長度全為奇數(shù)了），然后用一個輔助數(shù)組P記錄以每個字符為中心的最長回文串的信息。Pid記錄的是以字符strid為中心的最長回文串，當(dāng)以strid為第一個字符，這個最長回文串向右延伸了Pid個字符。    原串：    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    這里有一個很好的性質(zhì)，Pid-1就是該回文子串在原串中的長度（包括#）。如果這里不是特別清楚，可以自己拿出紙來畫一畫，自己體會體會。當(dāng)然這里可能每個人寫法不盡相同，不過我想大致思路應(yīng)該是一樣的吧。    好，我們繼續(xù)?，F(xiàn)在的關(guān)鍵問題就在于怎么在O（n）時間復(fù)雜度內(nèi)求出P數(shù)組了。只要把這個P數(shù)組求出來，最長回文子串就可以直接掃

4、一遍得出來了。    由于這個算法是線性從前往后掃的。那么當(dāng)我們準備求Pi的時候，i以前的Pj我們是已經(jīng)得到了的。我們用mx記在i之前的回文串中，延伸至最右端的位置。同時用id這個變量記下取得這個最優(yōu)mx時的id值。（注：為了防止字符比較的時候越界，我在這個加了#的字符串之前還加了另一個特殊字符$，故我的新串下標(biāo)是從1開始的）好，到這里，我們可以先貼一份代碼了。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)好寫。很方便吧，還記得我上面說的這個算法避免了很多不必要的重復(fù)匹配吧。這是什么意思呢，其實這就是一句代碼。if( mx > i     pi = MIN( p2*id-i, mx-i ;就是當(dāng)前面比較的最遠長度mx>i的時候，Pi有一個最小值。這個算法的核心思想就在這里，為什么P數(shù)組滿足這樣一個性質(zhì)呢?   （下面的部分為圖片形式）    看完這個算法，你有可能會覺得這種算法在哪會用到呢？其實回文串后綴數(shù)組也可以做。只是復(fù)雜度是O（n log n）的，而且一般情況下也不會刻意去卡一個log n的算法。可正好hdu就有這么一題，你用后綴數(shù)組寫怎么都得T（當(dāng)然應(yīng)該是