manacher算法能在O(n)时间内解决有关回文串的问题，而且算法本身也不长，noip前学学也无妨（虽然不太感觉能考）。
算法流程：
首先为了避免奇偶讨论我们在整个串前面添加一个字符‘@’，再整个串后面添加一个和 ‘@’不一样的字符（比如‘%’），然后每两个字符之间添加一个‘#’，比如aaa，就变成了@#a#a#a#%。
然后需要两个辅助变量：mx, id。mx代表当前的回文半径最远能到达的位置，所以存的是下标；id代表对应的回文中心。
对于算法计算到的 i ，计算回文半径p[i]时，令 i 关于id的对称点 j = 2 * id - i，然后分下面三种情况：
1.mx < i：必有p[i] >= 1，然后暴力扩展p[i]。
2.mx - i > p[j]：说明以 j 为中心的回文串全部包含在以 id 为中心的回文串中，而且一定全在 id的左边，根据对称性，必有p[i] = p[j]。
3.mx - i <= p[j]：说明 i 的会问半径不止mx - i，那么对于超出mx的部分，我们就暴力扩展。
复杂度：因为mx最多只会右移n次，所以时间复杂度O(n)。
统计答案：
这道题统计的是回文串长度，我们求的是添加完字符的回文串的半径，感觉上两者应该是相等的，但事实上应该是ans[i] = p[i] - 1。可以分一下两种情况考虑：
1.如果这一位是原串字符：那么算法得到的回文半径至少都是2，因为多算了‘#’，所以要减去1。
2.如果这一位是'#'：则两边肯定是原串字符，如果相等，就继续往两侧扩展，而两侧的又是'#'，所以半径至少是3，又多算了‘#’，所以还要减去1。
现在就可以解释为什么在字符串头和尾要添加两个不同的字符了，为什么不添或者添两个一样的就不行？
一个个解释：
1.不填，那么如果这个串就是回文串的话，他就会一直向两侧匹配，直到越界，然后就会发生些不可预料的事情。
2.添一样的：不仅不能防止越界，得到的答案还会加1.
上代码啦：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1.1e7 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n; 38 char s[maxn], t[maxn << 1]; 39 int p[maxn << 1]; 40 41 void init() 42 { 43 n = strlen(s); 44 t[0] = '@'; 45 for(int i = 0; i < n; ++i) t[i << 1 | 1] = '#', t[(i << 1) + 2] = s[i]; 46 n = (n << 1) + 2; 47 t[n - 1] = '#'; t[n] = '$'; 48 } 49 void manacher() 50 { 51 int mx = 0, id; 52 //id不用赋初值,因为对于第一次循环,一定有mx<1,于是id就被赋值成1了. 53 for(int i = 1; i < n; ++i) 54 { 55 if(mx > i) p[i] = min(p[(id << 1) - i], mx - i); 56 else p[i] = 1; 57 while(t[i - p[i]] == t[i + p[i]]) p[i]++; 58 if(i + p[i] > mx) mx = p[i] + i, id = i; 59 } 60 } 61 62 int main() 63 { 64 scanf("%s", s); 65 init(); manacher(); 66 int ans = 0; 67 for(int i = 0; i < n; ++i) ans = max(ans, p[i]); 68 write(ans - 1); enter; 69 return 0; 70 }