题目链接
最长回文子串 使用Manacher可O（n）的时间复杂度得到答案！
算法的精髓在于在没两个字符中插入一个'#'，实现每个回文串的长度都是奇数！
#include <bits/stdc++.h>
using namespace std;char s[100010], new_s[200010];
int len, p[200010];int Manacher()
{new_s[0] = '$', new_s[1] = '#';int j = 2;for(int i = 0; i<len; i++){new_s[j++] = s[i];new_s[j++] = '#';}new_s[j] = '\0';int id, mx = 0;int tmp_len = 0;for(int i = 1; i<j; i++){if(i < mx)p[i] = min(mx-i, p[2*id-i]);elsep[i] = 1;while(new_s[i + p[i]] == new_s[i - p[i]])p[i]++;if(i + p[i] > mx){mx = i + p[i];id = i;}tmp_len = max(tmp_len, p[i]-1);}return tmp_len;
}int main()
{cin >> s;len = strlen(s);cout<<Manacher();return 0;
}