題意：給出一個(gè)字符串，求出最長(zhǎng)回文字串。
 
 　　思路：一開始我直接上了后綴數(shù)組DC3的解法，然后MLE了。看了DISCUSS發(fā)現(xiàn)還有一種計(jì)算回文字串更加優(yōu)越的算法，就是manacher算法。就去學(xué)習(xí)了一下，
 
 　　這個(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)一起來考慮了。這一點(diǎn)一直是在做回文串問題中時(shí)比較煩的地方。這個(gè)算法還有一個(gè)很好的地方就是充分利用了字符匹配的特殊性，避免了大量不必要的重復(fù)匹配。
 
 　　算法大致過程是這樣。先在每?jī)蓚€(gè)相鄰字符中間插入一個(gè)分隔符，當(dāng)然這個(gè)分隔符要在原串中沒有出現(xiàn)過。一般可以用'#'分隔。這樣就非常巧妙的將奇數(shù)長(zhǎng)度回文串與偶數(shù)長(zhǎng)度回文串統(tǒng)一起來考慮了（見下面的一個(gè)例子，回文串長(zhǎng)度全為奇數(shù)了），然后用一個(gè)輔助數(shù)組P記錄以每個(gè)字符為中心的最長(zhǎng)回文串的信息。P[id]記錄的是以字符str[id]為中心的最長(zhǎng)回文串，當(dāng)以str[id]為第一個(gè)字符，這個(gè)最長(zhǎng)回文串向右延伸了P[id]個(gè)字符。
 　　原串： w aa bwsw f d
 　　新串： # 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ì)，P[id]-1就是該回文子串在原串中的長(zhǎng)度（包括'#'）。如果這里不是特別清楚，可以自己拿出紙來畫一畫，自己體會(huì)體會(huì)。當(dāng)然這里可能每個(gè)人寫法不盡相同，不過我想大致思路應(yīng)該是一樣的吧。
 　　好，我們繼續(xù)。現(xiàn)在的關(guān)鍵問題就在于怎么在O（n）時(shí)間復(fù)雜度內(nèi)求出P數(shù)組了。只要把這個(gè)P數(shù)組求出來，最長(zhǎng)回文子串就可以直接掃一遍得出來了sat答案
 　　由于這個(gè)算法是線性從前往后掃的。那么當(dāng)我們準(zhǔn)備求P[i]的時(shí)候，i以前的P[j]我們是已經(jīng)得到了的。我們用mx記在i之前的回文串中，延伸至最右端的位置。同時(shí)用id這個(gè)變量記下取得這個(gè)最優(yōu)mx時(shí)的id值。（注：為了防止字符比較的時(shí)候越界，我在這個(gè)加了'#'的字符串之前還加了另一個(gè)特殊字符'$',故我的新串下標(biāo)是從1開始的）托福答案
 　　/*****************************************************************************************************************************************************************/
 　　CODE:
 　　#include <set>
 　　#include <map>
 　　#include <stack>
 　　#include <cmath>
 　　#include <queue>
 　　#include <cstdio>
 　　#include <string>
 　　#include <vector>
 　　#include <iomanip>
 　　#include <cstring>
 　　#include <iostream>
 　　#include <algorithm>
 　　#define Max 2505
 　　#define FI first
 　　#define SE second
 　　#define ll long long
 　　#define PI acos（-1.0）
 　　#define inf 0x3fffffff
 　　#define LL（x） （ x 《 1 ）
 　　#define bug puts（"here"）
 　　#define PII pair<int,int>
 　　#define RR（x） （ x 《 1 | 1 ）
 　　#define mp（a,b） make_pair（a,b）
 　　#define mem（a,b） memset（a,b,sizeof（a））
 　　#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
 　　#define N 2000055
 　　using namespace std;
 　　char s[N] ;
 　　char str[N] ;
 　　int rad[N] ;
 　　int manacher （） {
 　　int len = strlen（s） ;
 　　int max = 0;
 　　str[0] = '$';
 　　str[1] = '#';
 　　int i = 0 ;
 
 　　for （； i < len; i++） {
 　　str[i * 2 + 2] = s[i];
 　　str[i * 2 + 3] = '#';
 　　}
 　　str[2 * len + 2] = 0;
 　　for （int i = 1; i < 2 * len + 2 ; i++） {
 　　rad[i] = 0;
 　　}
 　　int id = 0;
 　　for （i = 1; i < 2 * len + 2; i++） {
 　　if （max > i）
 　　rad[i] = min（rad[2 * id - i], rad[id] + id - i） ;
 　　else
 　　rad[i] = 1 ;
 　　while （str[i + rad[i]] == str[i - rad[i]]）
 　　rad[i] ++ ;
 　　if （rad[i] + i > max） {
 　　max = rad[i] + i;
 　　id = i;
 　　}
 　　}
 　　int mx = 0;
 　　for （i = 1; i < 2 * len + 2 ; i++） {
 　　if （mx < rad[i] - 1）
 　　mx = rad[i] - 1;
 　　}
 　　return mx;
 　　}
 　　int main（） {
 　　int ca = 0 ;
 　　while（scanf（"%s",s） != EOF） {
 　　if（strcmp（s , "END"） == 0）break ;
 　　printf（"Case %d: " , ++ ca） ;
 　　printf（"%d\n",manacher（）） ;
 　　}
 　　return 0 ;
 　　}