题目描述

给定一个字符串，请你求出其中的最长回文子串的长度。

例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 11。

输入格式
包含一个非空字符串。

输出格式
输出一个整数，表示给定字符串的最长回文子串的长度。

数据范围
给定字符串的长度不超过 1000。

输入样例：
Is PAT&TAP symmetric?
输出样例：
11
难度：简单
时/空限制：0.4s / 64MB
总通过数：44
总尝试数：114
来源：PAT甲级真题1040
算法标签

样例

blablabla

算法1

(中心扩散（暴力枚举）) $O(n^2)$

由于字符串长度小于1000，因此我们可以用 O(n2)O(n2) 的算法枚举所有可能的情况。
首先枚举回文串的中心 ii，然后分两种情况向两边扩展边界，直到遇到不同字符为止:

回文串长度是奇数，则依次判断 s[i−k]==s[i+k],k=1,2,3,…s[i−k]==s[i+k],k=1,2,3,…
回文串长度是偶数，则依次判断 s[i−k]==s[i+k−1],k=1,2,3,…s[i−k]==s[i+k−1],k=1,2,3,…
如果遇到不同字符，则我们就找到了以 ii 为中心的回文串边界。

时间复杂度分析：一共两重循环，所以时间复杂度是 O(n2)O(n2)。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    getline(cin,s);
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        for(int j=0;i-j>=0&&i+j<s.size();j++)
        {
            if(s[i-j]==s[i+j])
            {
               if(j*2+1>ans)
               {
                   ans=j*2+1;
               }
            }
            else
            break;
        }
        for(int k=i,j=i+1;k>=0&&j<s.size();k--,j++)
        {
            if(s[k]==s[j])
            {
                if(j-k+1>ans)ans=j-k+1;
            }
            else break;
        }
    }
    cout<<ans;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla