请选择 进入手机版 | 继续访问电脑版
  • 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

DP求最大回文子串长度

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

问题:给定字符串,求其最长回文子串的长度。回文串是形如”aba”, “abba”的对称字符串。例如:字符串“xabcbam”的最长回文字符串长度为5。

这个问题可以用动态规划(DP)来求解,其初始状态和转移方程如下:

实现的代码如下:


#include <stdio.h>
#include <string.h>

#define N 1024  //字符串最大长度
#define max(a, b) ((a) > (b) ? (a) : (b))

int g_cnt[N][N];  // g_cnt[i][j]表示i~j子串中最大回文长度, 默认全部初始化为0

//动态规划求最长回文子串的长度
int dp_maxlen(const char *s){
    int slen = strlen(s);
    if(slen >= N){
        fprintf(stderr, "exceed size:%d\n", N);
        return -1;
    }
    
    //长度为1的子串都是回文
    for(int i = 0; i < slen; ++i){
        g_cnt[i][i] = 1;
    }
    
    for(int len = 2; len <= slen; ++len){ //长度从小到大处理子串
        for(int i = 0; i < slen; ++i){
            int left = i;
            int right = i + len - 1;
            if( left < 0 || right >= slen){
                continue;
            }
            //左右两个字符相等,且中间部分也是回文
            if(s[left] == s[right] && g_cnt[left + 1][right - 1] == len - 2){
                g_cnt[left][right] = g_cnt[left + 1][right - 1] + 2;
            }
            else{
                g_cnt[left][right] = max(g_cnt[left + 1][right], g_cnt[left][right - 1]);
            }
        }
    }

    return g_cnt[0][slen - 1]; //整个字符串的最长回文长度即为所求值。
}

int main(int argc, char **argv){
    //测试用字符串
    const char *strings[] = {
        "abxabaxbmd",
        "aabbccddcbaabc",
        "aa",
        "aba",
        "a",
        "abba",
        "abcba",
        "xabcbam"
    };
    for(int i = 0; i < sizeof(strings) / sizeof(strings[0]); ++i){
        fprintf(stdout, "%s\t%d\n", strings[i], dp_maxlen(strings[i]));
    }
    return 0;
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
信息论常用概念发布时间:2022-05-14
下一篇:
揭开机器学习的神秘面纱:一张图弄懂协同过滤发布时间:2022-05-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap