1040 Longest Symmetric String（详解，技巧，字符串最长对称子串长度）

目录

题目

测试样例

输入样例

输出样例

提交结果截图

算法描述

带详细注释的源代码

题目

题目链接：

1040 Longest Symmetric Stringhttps://pintia.cn/problem-sets/994805342720868352/problems/994805446102073344

测试样例

输入样例

Is PAT&TAP symmetric?

输出样例

11

提交结果截图

算法描述

这题的算法有很多，我采用的是中心扩展法

理解起来也很简单，在字符串中寻找中心位置向两边扩展，双指针操作，得到从每个中心位置向两边扩展得到的最大对称子串长度，取其中的最大值即为该字符串的最大对称子串长度。

其中要注意的是，子串可能是奇数长度也可能是偶数长度，所以中心点可以选取的位置如下所示：

0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ ......  ^ n-6 ^ n-5 ^ n-4 ^ n-3 ^ n-2 ^ n-1

(其中，设字符串长度为n，字符串位置为0~n-1，而” ^ ”表示两个字符的中间位置)

可以选取的位置标记成了红色，当然0和n-1位置可以选取，但没必要（因为扩展出去长度也最多为1）。

所以只要从上述这n - 2 + n - 1 = 2n - 3个中心位置向两边扩展后得到的对称子串的长度的最大值即可。 

带详细注释的源代码

#include 
#include 
#include 
using namespace std;

//从某个位置向左右两边延伸查找
int find_len(string str, int left, int right)
{   //若是左右两端的字符相等则继续向左右两边延伸
    while(left >= 0 && right < str.length() && str[right] == str[left])
        right++, left--;
    return (right - left - 1);//返回对称子串的长度
}

int find_max_len(string str)
{
    int max_len = 1;
    int len = str.length();
    if(len < 2)//特殊情况，单独考虑
        return len;
    for(int i = 1; i < len - 1; i++)//逐个判断
    {
        //子串长度是奇数
        int odd_len = find_len(str, i, i);
        //子串长度是偶数
        int even_len = find_len(str, i, i+1);//这也是为什么for循环中是小于len-1
        if(max_len < max(odd_len, even_len))//取两者中更长的一者
            max_len = max(odd_len, even_len);
    }
    return max_len;
}

int  main()
{
    string str;
    getline(cin, str);//直接读入一行存入str
    cout<