HDU原題鏈接：傳送門
最長回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 33823 Accepted Submission(s): 12368
Problem Description
給出一個(gè)只由小寫英文字符a,b,c...y,z組成的字符串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字符串,如aba, abba等
Input
輸入有多組case,不超過120組,每組輸入為一行小寫英文字符a,b,c...y,z組成的字符串S
兩組case之間由空行隔開(該空行不用處理)
字符串長度len <= 110000
Output
每一行一個(gè)整數(shù)x,對應(yīng)一組case,表示該組case的字符串中所包含的最長回文長度.
Sample Input
aaaa
abab
Sample Output
4
3
題目分析——馬拉車算法
本題是Manacher(馬拉車)算法的一題模板題敷存，解決一個(gè)字符串的最長回文子串的問題尿贫，解題之前需要講述一下馬拉車算法的原理吉懊，我找了一篇講解這個(gè)算法比較好的博客：傳送門 參考前輩的文章后缩膝，在此也做出一些自己的總結(jié)鲸伴，以免時(shí)間久了自己產(chǎn)生遺忘冗疮，當(dāng)然馬拉車算法代碼量極少矾兜，但是其思想?yún)s需要仔細(xì)揣摩，做好準(zhǔn)備我們就開始吧巩检！
首先對于一個(gè)給出的字符串厚骗，例如aba，abba兢哭，abababadfsaa等领舰，最直觀的想到的去求它的最長回文子串的方法是從左到右遍歷每一個(gè)字符，以這個(gè)字符作為回文串的中心，然后不斷向兩邊擴(kuò)充提揍，直到不滿足后遍歷下一個(gè)字符，求出最長的回文子串的長度煮仇。但是這么做在字符串長度很長時(shí)效率很低劳跃，花費(fèi)大量的時(shí)間。
在介紹馬拉車算法之前浙垫，有必要先提及一個(gè)很巧妙且重要的方法刨仑，不知你是否發(fā)現(xiàn)，通過上述的方法求回文子串夹姥，我們總是以一個(gè)字符為出發(fā)點(diǎn)向兩邊匹配杉武，那么每次所匹配出來的回文串都是奇數(shù)，而無法判斷abba這樣的偶數(shù)回文串辙售，所以就產(chǎn)生了一種拼接字符串的神奇方法轻抱，將一個(gè)初始的字符串用一個(gè)不會(huì)出現(xiàn)的字符隔開，例如#a#b#a#旦部，#a#b#b#a#祈搜，你驚奇的發(fā)現(xiàn)，無論是奇數(shù)還是偶數(shù)的字符串經(jīng)過這么處理之后不但不會(huì)改變它原有的對稱特性（只是長度好像變長了一倍士八？因?yàn)?也是一個(gè)字符容燕，且它的存在不會(huì)打斷原有的回文特性，只是增長了而已婚度，放心下面會(huì)講明它變長的長度是有著一個(gè)固定的數(shù)學(xué)關(guān)系的）蘸秘，而且所有的串都變成了奇數(shù)串（奇+偶=奇，偶+奇=奇）蝗茁，秒按茁病！
那么我們得到了一個(gè)類似#a#b#a#的串之后該怎么做呢哮翘，別急灰粮，我們需要將這個(gè)字符再做一點(diǎn)處理，在它最前面插入一個(gè)不會(huì)出現(xiàn)且不同于#的字符忍坷，就像$#a#b#a#這樣粘舟，這么做有一個(gè)好處，就是我們將實(shí)際會(huì)用于算法求解的字符從下標(biāo)0開始轉(zhuǎn)化成了從下標(biāo)1開始佩研，后面我們遍歷時(shí)也是從下標(biāo)1開始的柑肴，這樣第一個(gè)有效字符的位置就是s[1]，第二個(gè)就是s[2]旬薯，方便后面我們使用馬拉車算法進(jìn)行推導(dǎo)晰骑。
對于一個(gè)字符串如：$#a#a#b#a#a#，我們設(shè)P[i]為以第i個(gè)字符為回文串中心時(shí)最長的回文半徑(包含S[i]本身)，那么遍歷P[i]就可以找出最長的回文子串的長度
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | $ | # | a | # | a | # | b | # | a | # | a | # |
| P | 1 | 1 | 2 | 3 | 2 | 1 | 6 | 1 | 2 | 3 | 2 | 1 |
| 下標(biāo) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| s | a | a | b | a | a |
| p | 1 | 1 | 3 | 1 | 1 |
此時(shí)就會(huì)有人提出疑問硕舆，這個(gè)是我拼接之后的字符串呀秽荞，求出它的最長回文子串的長度與求拼接前的最長回文子串長度有什么關(guān)系嗎？有關(guān)系抚官，你發(fā)現(xiàn)上述拼接后的字符串最長回文子串是以i==6為中心的扬跋，就是以b這個(gè)字符為中心，那么你驚奇的發(fā)現(xiàn)原字符串最長回文子串一定也是以b為中心的凌节，因?yàn)槲覀兩厦婢吞岬搅饲仗唇拥?不會(huì)影響原字符串的回文特性，只是讓它們在原先的基礎(chǔ)上都變長了而已倍奢，而它們之間的關(guān)系很顯然是2倍關(guān)系P[i]==2*p[i]朴上，由于題目所求的是原字符串的最長回文子串的長度，那么答案就是P[i]-1卒煞，因?yàn)槲覀冏允甲越K用拼接后的字符串參與推導(dǎo)痪宰，所以只要關(guān)注P[i]數(shù)組即可。
那么所有問題的矛頭都指向一處畔裕！p[i]怎么求（下面都用小寫的p代表拼接后字符串的以i為回文中心的最長回文半徑酵镜，頻繁切換大寫讓我覺得有些異樣w(?Д?)w），馬拉車算法柴钻，啟動(dòng)淮韭！因?yàn)槲覀兪菑淖蟮接冶闅vi的，在計(jì)算p[i]時(shí)我們要確保p[1]~p[i-1]已經(jīng)求出贴届，這樣才能借助回文串的對稱特性靠粪，也是就前面求出來的p[j]減少后面p[i]的匹配次數(shù)（此時(shí)你可能不明白這句話的含義，且仔細(xì)往下看）毫蚓，我們要用到兩個(gè)輔助的變量id和mx占键，id為i之前的一個(gè)能向右伸展的最遠(yuǎn)的回文串的回文串中心，mx為以id為回文中心的這個(gè)回文串往右（往左）能伸展到的最遠(yuǎn)的距離
還是借助一下圖來更加清晰的展示
其中j是i關(guān)于id的對稱點(diǎn)元潘，j=2*id-i畔乙，這個(gè)自行推一下便可，那么此時(shí)上圖展示的只是其中一種情況翩概，當(dāng)以i為回文中心的時(shí)i點(diǎn)在左側(cè)一個(gè)向右伸展足夠長至把i點(diǎn)包括其中的回文串內(nèi)牲距，即i<mx，當(dāng)這種情況時(shí)钥庇，又分為兩種小的情況
- 當(dāng)以p[j]即p[2*id-i]為中心的回文串長度沒有超過以id為對稱中心的回文串的左邊界
由于以i和j為中心的回文串是關(guān)于id對稱的兩個(gè)子串牍鞠，所以p[i]自然而然和p[j]相等，即p[i]=p[2*id-i]
- 當(dāng)以p[j]為中心的回文串左邊界超過以id為回文中心的回文串的左邊界
左邊的綠色線代表超過id左邊界的回文串评姨，此時(shí)难述，由于對稱關(guān)系，只能得知以i為中心的回文串在id右邊界之內(nèi)的部分和以j為中心的回文串在id左邊界之內(nèi)的部分是對稱的，而以i為中心的超過右邊界的部分則只能老老實(shí)實(shí)向兩側(cè)匹配胁后，所以在這兩種情況下店读，如果p[2 * id-i]>=mx-i+1，則說明超過左邊界攀芯，則只取用邊界內(nèi)的對稱部分p[i]=mx-i+1屯断，如果p[2 * id-i]<mx-i+1，說明不超過左邊界敲才，則由于p[2 * id-i]和p[i]對稱裹纳，直接繼承择葡，p[i]=p[2 * id-i]紧武。
//在借助回文串i前已經(jīng)計(jì)算出的數(shù)據(jù)減少匹配次數(shù)后，依舊要老老實(shí)實(shí)調(diào)用下面的函數(shù)去匹配
while(i-p[i]>=1&&i+p[i]<=len*2+1){ //下標(biāo)向左不越界敏储，下標(biāo)向右不越界
if(s[i-p[i]]==s[i+p[i]]) p[i]++; //初始化p[i]都是1,至少回文半徑是1
else break;
}
不要忘記還有一種大情況阻星，就是i點(diǎn)在mx的邊界或者外面時(shí)
在這兩種情況下，p[i]是否對稱都要從超過id右邊界（mx）的地方開始一個(gè)一個(gè)首尾比較已添，所以沒有辦法借助p[j]來減少預(yù)匹配的次數(shù)妥箕，直接調(diào)用上面的函數(shù)老老實(shí)實(shí)匹配吧
要注意的是隨著每一次i的遍歷之后，如果mx能更加向右延伸更舞，即p[i]+i-1>p[id]+id-1畦幢，-1是因?yàn)橹貜?fù)加點(diǎn)了，仔細(xì)推理一下便可缆蝉，例如id=5宇葱，p[id]=3，則mx=p[id]+id-1=7刊头，那么要更新id的位置為i黍瞧，更新mx為p[i]+i-1，確保id永遠(yuǎn)是右邊界最接近下一個(gè)要遍歷的i點(diǎn)那個(gè)對稱中心
示例代碼
#include<iostream>
#include<string>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=110000+10;
char s[N*2];
int p[N*2];
int main(){
while(scanf("%s",s)!=EOF){
int len=strlen(s);
for(int i=len;i>=1;i--){
s[i*2+1]='#';
s[i*2]=s[i-1];
// s[i*2-1]='#'; 具體的拼接字符串的方法每個(gè)人寫的都有些細(xì)微的差別
}
s[1]='#';
s[0]='$';
// printf("%s\n",s);
// memset(p,0,sizeof(p));
int maxx=1; //用于統(tǒng)計(jì)最后的輸出結(jié)果
fill(p,p+2*N,1);
int id=1,mx=1; //mx=id+p[id]-1==1 代表i前的以id為中心的回文串可以達(dá)到的最右邊的邊界
for(int i=2;i<=len*2+1;i++){
if(i<mx){
p[i]=min(p[2*id-i],mx-i+1); //i關(guān)于id的對稱點(diǎn)2*id-i原杂，回文串半徑可能超過mx-i+1印颤，有可能更短
}
//上述if語句借助了回文串的對稱特性減少匹配次數(shù)
//此時(shí)如果p[2*id-i]>=mx-i+1，則相對的i的回文串半徑也可能更長
//或者i本身就在mx的外面穿肄，則無法借助上述if語句減少以i為中心的回文串的匹配次數(shù)
while(i-p[i]>=1&&i+p[i]<=len*2+1){
if(s[i-p[i]]==s[i+p[i]]) p[i]++;
else break;
}
//需要i每往后一次就要實(shí)時(shí)更新id和mx的大小
if(p[i]+i-1>mx){
mx=p[i]+i-1;
id=i;
}
if(p[i]>maxx) maxx=p[i];
}
printf("%d\n",maxx-1);
}
return 0;
}
