回文串定義：“回文串”是一個(gè)正讀和反讀都一樣的字符串，比如“l(fā)evel”或者“noon”等等就是回文串。回文子串，顧名思義，即字符串中滿足回文性質(zhì)的子串。
經(jīng)常有一些題目圍繞回文子串進(jìn)行討論，比如POJ3974最長(zhǎng)回文，求最長(zhǎng)回文子串的長(zhǎng)度。樸素算法是依次以每一個(gè)字符為中心向兩側(cè)進(jìn)行擴(kuò)展，顯然這個(gè)復(fù)雜度是O(N^2)的，關(guān)于字符串的題目常用的算法有KMP、后綴數(shù)組、AC 自動(dòng)機(jī)，這道題目利用擴(kuò)展KMP可以解答，其時(shí)間復(fù)雜度也很快O(N*logN)。但是，今天筆者介紹一個(gè)專門針對(duì)回文子串的算法，其時(shí)間復(fù)雜度為O(n)，這就是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)回文半徑，也就是P[i]記錄以Str[i]字符為中心的最長(zhǎng)回文串半徑。P[i]最小為1，此時(shí)回文串為Str[i]本身。
我們可以對(duì)上述例子寫出其P 數(shù)組，如下
新串： # a # b # a # a # b #
P[] : 1 2 1 4 1 2 5 2 1 2 1
我們可以證明P[i]-1 就是以Str[i]為中心的回文串在原串當(dāng)中的長(zhǎng)度。
證明：
1、顯然L=2*P[i]-1 即為新串中以Str[i]為中心最長(zhǎng)回文串長(zhǎng)度。
2、以Str[i]為中心的回文串一定是以#開(kāi)頭和結(jié)尾的，例如“#b#b#”或“#b#a#b#”所以L 減去最前或者最后的‘#’字符就是原串中長(zhǎng)度 的二倍，即原串長(zhǎng)度為(L-1)/2，化簡(jiǎn)的P[i]-1。得證。 依次從前往后求得P 數(shù)組就可以了，這里用到了DP(動(dòng)態(tài)規(guī)劃)的思想， 也就是求P[i] 的時(shí)候，前面的P[]值已經(jīng)得到了，我們利用回文串的特殊性質(zhì)可以進(jìn)行一個(gè)大大的優(yōu)化。
先把核心代碼貼上：
for (i = 0; i < len;="" i++){="" if="" (maxid=""> i){ p[i] = min(p[2*id - i], maxid - i); } else{ p[i] = 1; } while (newstr[i+p[i]] == newstr[i-p[i]]) p[i]++; if (p[i] + i > maxid){ maxid = p[i] + i; id = i; } if (ans < p[i])="" ans="p[i];">
為了防止求P[i]向兩邊擴(kuò)展時(shí)可能數(shù)組越界，我們需要在數(shù)組最前面和最后面加一個(gè)特殊字符，令P[0]=‘$’最后位置默認(rèn)為‘\0’不需要特殊處理。此外，我們用MaxId 變量記錄在求i 之前的回文串中，延伸至最右端的位置，同時(shí)用id 記錄取這個(gè)MaxId 的id 值。通過(guò)下面這句話，算法避免了很多沒(méi)必要的重復(fù)匹配。
if (maxid > i){ p[i] = min(p[2*id - i], maxid - i); }
那么這句話是怎么得來(lái)的呢，其實(shí)就是利用了回文串的對(duì)稱性，如下圖，
j=2*id-1 即為i 關(guān)于id 的對(duì)稱點(diǎn)，根據(jù)對(duì)稱性，P[j]的回文串也是可以對(duì)稱到i 這邊的,但是如果P[j]的回文串對(duì)稱過(guò)來(lái)以后超過(guò)MaxId 的話，超出部分就不能對(duì)稱過(guò)來(lái)了，如下圖，
所以這里P[i]為的下限為兩者中的較小者，p[i]=Min(p[2*id-i],MaxId-i)。算法的有效比較次數(shù)為MaxId 次，所以說(shuō)這個(gè)算法的時(shí)間復(fù)雜度為O(n)。
下面就貼一個(gè)具體代碼，求解最長(zhǎng)回文字符串的代碼：
#include
#include #include using namespace std;const int MAX = 100001;int len, p[2*MAX];char str[2*MAX], newstr[2*MAX];void change(){ int i; newstr[0] = '@'; newstr[1] = '#'; for (i = 0; i < len;="" i++){="" newstr[2*i="" +="" 2]="str[i];" newstr[2*i="" +="" 3]='#' ;="" }="" newstr[2*len="" +="" 2]='\0' ;="" return="" ;}void="" manacher(){="" int="" i,="" j,="" id,="" maxid="0," ans="1;" len="2" *="" len="" +="" 2;="" for="" (i="0;" i="">< len;="" i++){="" if="" (maxid=""> i){ p[i] = min(p[2*id - i], maxid - i); } else{ p[i] = 1; } while (newstr[i+p[i]] == newstr[i-p[i]]) p[i]++; if (p[i] + i > maxid){ maxid = p[i] + i; id = i; } if (ans < p[i])="" ans="p[i];" }="" for="" (i="id," j="0;" i="">< id="" +="" ans;="" i++){="" if="" (newstr[i]="" !='#' ){="" str[j]="newstr[i];" j++;="" }="" }="" str[id+ans]='\0' ;="" cout="">< ans="" -="" 1="">< '="" '="">< str="">< endl;="" return="" ;}int="" main(){="" while="" (scanf('%s',="" &str)){="" if="" (strcmp(str,="" 'end')="=" 0)="" break;="" len="strlen(str);" change();="" manacher();="" }="">
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
