xindoo is
always here

poj 1159 Palindrome(最长公共子串)


大概题意就是求最少添加多少个字符可以把长度为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;
}
打赏
未经允许不得转载:XINDOO » poj 1159 Palindrome(最长公共子串)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏