题目描述

最长回文子串长度

思路

首先对字符串进行处理，将字符串两两字符之间插入‘ * ’，得到长度为奇数的字符串
这样可以避免 abba 以及 aba 两种情况回文的判断

算法1

暴力遍历

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string st,s;
    getline(cin,st);

    //字符串预处理(将字符串两两字符之间插入‘*’，得到长度为奇数的字符串)
    for(int i=0;i<st.size();++i)
    {
        s+="*";
        s+=st[i];
    }
    s+="*";

    int n=s.size();
    int res=0;
    for(int i=1;i<n;++i)
    {
        int t=min(i,n-i),j=1;
        for(;j<=t;++j)
        {
            if(s[i-j]!=s[i+j])
                break;
        }
        if(s[i]=='*')
            res=max(res,j-1);
        else
            res=max(res,(j-1)/2*2+1);
    }
    cout<<res;

}

算法2

字符串哈希（提供思路）