首页 > 代码库 > poj 1159 Palindrome (LCS)
poj 1159 Palindrome (LCS)
链接:poj 1159
题意:给定一个字符串,求最少添加多少个字符可使得该字符串变为回文字符串
分析:设原序列S的逆序列为S‘ ,最少需要补充的字母数 = 原序列S的长度 - S和S‘的最长公共子串长度
原因:要求最少添加几个字符,我们可以先从原串中找到一个最长回文串,然后对于原串中不属于这个回文串的字符,在它关于回文串中心的对称位置添加一个相同字符即可。那么需要添加的字符数量即为n-最长回文串长度。
最长回文串可以看作是原串中前面和后面字符的一种匹配(每个后面的字符在前面找到一个符合位置要求的与它相同的字符)。这种的回文匹配和原串与逆序串的公共子序列是一一对应的(一个回文匹配对应一个公共子序列,反之亦然),而且两者所涉及到的原串中的字符数量是相等的,也就是最长公共子序列对应最长回文串。
注意:这题用 如果用静态数组 5001*5001 会内存超限,我用的 short 过了,不过可以用滚动数组
#include<stdio.h> short dp[5005][5005]; int max(int a,int b) { return a>b?a:b; } int main() { int n,i,j; char s[5005],t[5005]; while(scanf("%d",&n)!=EOF){ getchar(); for(i=0;i<n;i++){ s[i]=getchar(); t[n-i-1]=s[i]; //求逆序 dp[i][0]=dp[0][i]=0; //初始化 } s[n]=t[n]=0; for(i=0;i<n;i++) //求原序与逆序的最长公共子串 for(j=0;j<n;j++){ if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1; else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); } printf("%d\n",n-dp[n][n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。