算法：最长回文子串长度

冷不防 2022-07-26 00:06 227阅读 0赞

#### 动态规划： ####

最长回文子串：连续+回文  
公式  
p\[i,j\] =  
1)if(str\[i\] == str\[j\]) p\[i\]\[j\] = 2+p\[i+1\]\[j-1\]  
2)if(str\[i\]!=str\[j\]) p\[i\]\[j\] = max(p\[i\]\[j-1\], p\[i+1\]\[j\])  
p\[i\]\[i\] = 1;

需要注意的是，在求解的时候
    计算的长度由短到长，否则在公式中依赖较短的长度的值不可得会造成错误。
    
    //最长回文子串
    int finddp1(string  str)
    {
        int len = str.size();
        vector<vector<int> > dp1(len, vector<int>(len,0));
        for(int i = 0; i < len; i++)
        {
            dp1[i][i] = 1;
        }
        for(int i = 1; i < len; i++)            //串长度
        {
            for(int j = 0; j+i < len; j++)      //串的起始和结束下标
            {
                if(str[j] == str[j+i])
                {
                    dp1[j][j+i] = 2 + dp1[j+1][j+i-1];
                }
                else
                {
                    dp1[j][j+i] = max(dp1[j][j+i-1], dp1[j+1][j+i]);
                }
            }
        }
        return dp1[0][len-1];
    }
    
    int main()
    {
        string input;
        cin>>input;
        printf("%d\n",finddp1(input));
        return 0;
    }

![这里写图片描述][20160404102249922]

[20160404102249922]: /images/20220724/8dadf57ee315423992aa0f6f3e50688b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，227人围观）

还没有评论，来说两句吧...

相关阅读

相关最长回文子串

[题目：给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。][s_ s] > 解题思路：动态规划 > 动态规划的

怼烎@/ 2024年03月08日 04:08/ 0 赞/ 102 阅读

相关最长回文(manacher算法,最大回文子串)

Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba,

刺骨的言语ヽ痛彻心扉/ 2024年02月17日 19:27/ 0 赞/ 42 阅读

相关算法：最长回文子串。

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。示例 > 输入: "babad" > 输出: "b

àì夳堔傛蜴生んèń/ 2023年02月24日 03:57/ 0 赞/ 5 阅读

相关算法题：最长回文子串

算法题：最长回文子串题目描述示例 python代码执行效率题目描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假

布满荆棘的人生/ 2022年12月27日 08:43/ 0 赞/ 204 阅读

相关最长回文子串

最长回文子串 1、参考资料 https://leetcode-cn.com/problems/longest-palindromic-substring/ htt

╰半夏微凉°/ 2022年12月08日 05:24/ 0 赞/ 226 阅读

相关最长回文子串

/ 最长回文子串输入一个字符串s，请找出s中最长回文子串的长度 dp[i][j]是子串s[i...j]中的最长回文子串的长度 / public clas

清疚/ 2022年10月29日 12:23/ 0 赞/ 223 阅读

相关最长回文子串

回文串指给定的字符串，正着读和反着读都是一样的。如ADA，反过来还是ADA即为回文串。最长回文子串指查找一给定字符串中最长的回文串。通常有以下4种解法。主要考虑的是时间复杂

雨点打透心脏的1/2处/ 2022年08月07日 04:43/ 0 赞/ 263 阅读

相关算法：最长回文子串长度

动态规划：最长回文子串：连续+回文公式 p\[i,j\] = 1)if(str\[i\] == str\[j\]) p\[i\]\[j\] = 2+p\[

冷不防/ 2022年07月26日 00:06/ 0 赞/ 228 阅读

相关最长回文子串

include <iostream> include <vector> include <string> include <algori

淩亂°似流年/ 2022年06月17日 06:53/ 0 赞/ 289 阅读

相关最长回文子串

【题目】给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。输入: “babad” 输出: “bab” 注意: “aba”

骑猪看日落/ 2021年09月21日 05:28/ 0 赞/ 383 阅读