题解 | #密码截取#

//马拉车+1
#include <bits/stdc++.h>
using namespace std;

string Manacher(string tmp)
{
    string str = "$#";
    for(int i = 0; i<tmp.length(); i++)
    {
        str+=tmp[i];
        str+='#';
    }
    int* len = new int[str.size()];    //存储以str每个字符为中心最长回文串的半径
    int ioo = 0, max = 0; 
    int maxlen = 0, start = 0; //总是忘记初始化为0，哎
    for(int i = 1; i<str.length(); i++)
    {
        if(i<max)
        {
            if(len[2*ioo-i] < max-i)
                len[i] = len[2*ioo-i];
            else
                len[i] = max-i;
        }
        else 
            len[i] = 1;
        
        while(str[i+len[i]] == str[i-len[i]] && i+len[i]<str.length() && i-len[i]>=0)
            len[i]++;
        
        if(i+len[i] > max)    //更新max和ioo 
        {
            max = i+len[i];
            ioo = i;
        }
        
        if(len[i]-1 > maxlen)    //更新maxlen和start 为当前最长回文串（原字符串中）的长度和起始位置
        {
            maxlen = len[i] - 1;
            start = (i - len[i]) / 2;
        }
    }
    delete []len;   //delete不能忘
    return tmp.substr(start, maxlen);
}
 
int main()
{
    string input_str;
    cin >> input_str;
    string out_str = Manacher(input_str);
    //cout << out_str;
    cout << out_str.length();

    return 0;
}