求一个字符串的最长回文子串长度
manacher利用了回文的性质,达到线性时间.
首先加一个小优化,在每两个字符之和头尾加没有出现的符号,这里我们使用”^”,”@”和”#”,这样可以使得字符串的长度为奇数,这样就不用讨论回文串长度时奇数还是偶数的问题了

abcde->^#a#b#c#d#e#@

记p[i]表示i能向两边推的最大距离(包括i)的最大距离,求出的最大值就是p[i] - 1,增加字符优化以后回文子串的长度是2*p[i] - 1,那么没增加字符就是p[i] - 1.

假设我们现在要求p[i],我们当前能达到的最右端的下标是R,对应的中点是pos,j是i的对称点.
1.i < R:
(1)L~R是回文,p[i] = p[j] (i的最长回文和j的最长回文相同)

(2)j的最长回文跳出L,那么i的最长回文不一定是j的最长回文,但是蓝色部分肯定满足

综上,p[i] = min(p[2*pos-i],R-i)
2.i >= R
后面的情况未知只能暴力处理

//马拉车模板题
#include <bits/stdc++.h>
using namespace std;
string s, str;
const int N = 2e6 + 10;//注意:使用manacher算法时数组要开大点
int p[N];
void add()
{
    str += "^";
    for(int i = 0; i < s.size(); i++)
    {
        str += "#";str += s[i];
    }
    str += "#";str += "@";
}

int manacher()
{
    add();
    int R = 0, mid = 0, ans = -1;
    for(int i = 1; i < str.size(); i++)
    {
        p[i] = i < R ? min(p[2 * mid - i], R - i) : 1; //进行三种情况的判断
        while(str[i + p[i]] == str[i - p[i]])   p[i]++;//进行中心拓展
        if(i + p[i] > R)                               //如果拓展的坐标超过当前的范围,那么就更新右边界 
        {
            R = i + p[i];
            mid = i;
        }
        ans = max(ans, p[i] - 1);
    }
    return ans;
}
int main()
{
    int n = 0;
    while(cin >> s && s != "END")
    {
        //注意:每次使用manacher算法的时候,如果开了全局变量就没必要传参数了,如果要传参数的话也不要传同名的参数名
        str.clear();
        n++;cout << "Case " << n << ": " << manacher() << '\n';
    }
}