题解 | #最长回文子串#

// 菜人看懂马拉车真的用了好久   
#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 maxlen = 0, start = 0;
    int *len = new int [1000];   //new1000个int。原字符串最长350，外加351个#和1个$ 
    int ioo = 0;       //ioo为当前能延申到最右端的回文串的中心位置，不一定四最长的
    int max = 0;     //max是当前能延申到最右端回文串的末端，可以理解为"水平"方向的max
    for(int i = 1; i<str.length(); i++)
    {
        if(i<max)
        {
            if(len[2*ioo-i] < max - i)   //2*ioo-i  是i关于ioo对称点
                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] += 1;
        
        if(i+len[i] > max)  //更新max和ioo，是当前延伸到最右的回文子串的末端下标和中心下标
        {
            max = i+len[i];
            ioo = i;
        }
        
        if(len[i] - 1 > maxlen)   //这里是没加$和#之前的原字符串tmp的长度 所以是len[i]-1;
        {
            maxlen = len[i] - 1;
            start = (i - len[i])/2;
        }
    }
        delete len;
    return tmp.substr(start,maxlen);    
}

int main()
{ 
    string input_str; cin >> input_str;
    string out_str ;
    out_str = Manacher(input_str);
//     cout<<out_str;
    cout << out_str.length();
     
    return 0;
}