代码注释：
1 const int MAXN = 110009; 2 char ma[MAXN * 2]; //因为要添加'#',所以长度要开两倍 3 int mp[MAXN * 2]; 4 char s[MAXN]; 5 6 void Manacher(char s[], int len) { 7 8 // 1. 构造字符串,添加'#',使长度变为奇数(2 * len - 1) 9 int l = 0; 10 ma[l++] = '$'; // 设置边界 11 ma[l++] = '#'; 12 for(int i = 0; i < len; i ++) { 13 ma[l++] = s[i]; 14 ma[l++] = '#'; 15 } 16 ma[l] = 0; 17 18 // 核心: 求回文半径, 回文半径包括中心点 19 int mx = 0; // mx代表可达的最右值 20 int id = 0; // id代表mx的中心 21 for(int i = 0; i < l; i ++) { 22 mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1; 23 while(ma[i + mp[i]] == ma[i - mp[i]]) { 24 mp[i] ++; 25 } 26 if(i + mp[i] > mx) { 27 mx = i + mp[i]; 28 id = i; 29 } 30 } 31 32 } 33 34 int main() 35 { 36 37 while(scanf("%s", s) != EOF) { 38 int len = strlen(s); 39 Manacher(s, len); 40 int ans = 0; 41 for(int i = 0; i < 2 * len + 2; i ++) { // 寻找最长的回文半径，即回文串长度 42 ans = max(ans, mp[i] - 1); // 回文半径减1就是原回文串的长度(回文半径中虚加了#) 43 cout << mp[i] << " "; 44 } 45 printf("%d\n", ans); 46 } 47 48 return 0; 49 }