Chen

最长回文子串(动态规划解法)
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最...
扫描右侧二维码阅读全文
13
2019/03

最长回文子串(动态规划解法)

对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。

输入格式:
输入在一行中给出长度不超过1000的非空字符串。

输出格式:
在一行中输出最长对称子串的长度。

输入样例:

Is PAT&TAP symmetric?

输出样例:

11

思路

pal数组标记位于j~i之间串是否为回文子串
若判断j~i间是否为回文子串,需依赖于 j+1 ~ i-1间子串类型,依此类推
直到依赖项为x或者xy,(x,y未知)(仔细体会为什么是这样)
i-j<2 :用于判断x或者xy的情况,当然不要忽略&&的短路效应

代码

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

bool pal[MAXN][MAXN]= {0};
int longestPalindrome(string str)
{
    int n=str.length();
    int maxLen=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i; j>=0; j--)
        {
            if(str[i]==str[j] && (i-j<2 || pal[j+1][i-1]==true))
            {
                pal[j][i]=true;
                maxLen=max(maxLen, i-j+1);
            }
        }
    }
    return maxLen;
}
int main()
{
    string str;
    getline(cin,str);
    cout<<longestPalindrome(str)<<endl;
    return 0;
}
Last modification:May 10th, 2019 at 05:31 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment