团体程序设计天梯赛
L2-008 最长对称子串
Manacher算法。参考：F05 Manacher(马拉车)
预处理字符串：开至少2N+10大小的新字符数组s，令s[0] = '$'(哨兵)，然后使每一个原字符串的字符，其前面和后面的一个位置都有'#'.
数组d[i]表示在新字符串中以i为中心的最大回文串的长度的一半(包括自身)，d[i] - 1即为在原字符串中回文串的长度。
求d[i]需要维护一个区间[l, r]，如下图，当回文区间超过这个区间时，更新这个区间。算法的时间复杂度是$O(n)$.
#include <bits/stdc++.h>
using namespace std;
char str2[2010];
int d[2010];
void getd(char s[], int n){
d[1] = 1;
for(int i = 2, l, r = 1; i <= n; i++){
if(i <= r) d[i] = min(d[l + r - i], r - i + 1);
while(s[i - d[i]] == s[i + d[i]]) d[i]++;
if(i + d[i] - 1 > r) l = i - d[i] + 1, r = i + d[i] - 1;
}
}
int main(){
string str1;
getline(cin, str1);
str2[0] = '$';
int n = 0, i = 0;
while(n <= (int)str1.size() - 1){
str2[++i] = '#';
str2[++i] = str1[n++];
}
str2[++i] = '#';
n = i;
getd(str2, n);
int length = *max_element(d + 1, d + 1 + n) - 1;
// for(int i = 1; i <= n; i++) cout << str2[i] << ' ';
// cout << endl;
// for(int i = 1; i <= n; i++) cout << d[i] << ' ';
// cout << endl;
cout << length << endl;
return 0;
}