給出一個隻由小寫英文字元a,b,c...y,z組成的字元串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字元串,如aba, abba等
Input
輸入有多組case,不超過120組,每組輸入為一行小寫英文字元a,b,c...y,z組成的字元串S
兩組case之間由空行隔開(該空行不用處理)
字元串長度len <= 110000
Output
Sample Input
aaaa
abab
Sample Output
4
3
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int Manacher(string s){
string t = "$#";
for(int i=0;i<s.size();i++){
t+=s[i];
t+="#";
}
vector<int>p(t.size(),0);
int mx=0,id=0,resLen=0,resCenter=0;
for(int i=1;i<t.size();i++){
p[i]=mx>i?min(p[2*id-i],mx-i):1;
while(t[i+p[i]]==t[i-p[i]]) ++p[i];
if(mx<i+p[i]){
mx=i+p[i];
id=i;
}
if(resLen<p[i]){
resLen=p[i];
resCenter=i;
}
}
string str=s.substr((resCenter-resLen)/2,resLen-1);
return str.length();
}
int main(){
string str;
while(cin>>str){
printf("%d\n",Manacher(str));
}
return 0;
}