poj 1159 Palindrome(最长公共子串)

xindoo

发布于 2021-01-22 12:55:01

4110

发布于 2021-01-22 12:55:01

文章被收录于专栏：XINDOO的专栏XINDOO的专栏

大概题意就是求最少添加多少个字符可以把长度为N的字符串编程回文串。

则需要最少需要补充的字母数 = 原序列S的长度 — S和S'的最长公共子串长度

S'为原串的逆串。

关于求最长公共子串，用到的是动态规划

伪代码如下

if( i ==0 || j == 0 ) {

MaxLen(i, j) = 0 //两个空串的最长公共子序列长度当然是0

}

else if( s1[i] == s2[j] )

MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;

else {

MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j));

}

具体可参考算法导论第三版222页

//2013-05-30-19.58
//poj 1159
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 5005;
short dp[maxn][maxn];
char s1[maxn], s2[maxn];
int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        getchar();
        for (int i = 1; i <= n; i++)
        {
            scanf("%c", &s1[i]);
            s2[n-i+1] = s1[i];
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (s1[i] == s2[j])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        printf("%d\n", n-dp[n][n]);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2013-05-30，如有侵权请联系 cloudcommunity@tencent.com 删除

max