题解 | #回文串#

using namespace std;
#define int long long
const int N=1e5+5;
int p[N];
signed main(){
    string s,t;
    while(cin>>s){
        int n=s.size();
        int len=0;
        t="^#";//字符串前加^后加$可以避免判断越界（只要前后添加的两符号不同且字符串中不会出现即可） 
        for(int i=0;i<n;i++){
            t+=s[i];
            t+='#';
        }
        t+='$';
        memset(p,0,sizeof(p));
        int c=0,r=0;
        //c表示回文串的中心，r表示回文串的右边半径 
        //r=c+p[i]; 
        for(int i=1;i<t.size();i++){
            int i_mirror=2*c-i;//i_mirror表示当前需要求的第 i 个字符关于 C 对应的下标 
            if(i<r){
                p[i]=min(r-i,p[i_mirror]);//防止超出r 
            }        
            else{
                p[i]=0; //等于r 
            }
            //中心拓展法 
            while(t[i-1-p[i]]==t[i+1+p[i]]){
                p[i]++;
            }
            //判断是否需要更新r 
            if(i+p[i]>r){
                c=i;
                r=i+p[i];
            }
        }    
        int maxx=0;
        for(int i=1;i<t.size();i++){
            maxx=max(maxx,p[i]);//求最长回文串的长度
        }
        cout<<maxx<<endl;
    }
    return 0;
}