首页 > 代码库 > POJ159:Palindrome(LCS小应用 回文）
POJ159:Palindrome(LCS小应用 回文）
地址：http://poj.org/problem?id=1159
题目需求：
给你一个字符串，求最少添加多少字符可以使之构成回文串。
题目解析：
简单做法是直接对它和它的逆序串求最长公共子序列长度len。n-len即为所求。(n为原串长度)
即 ： 最少补充的字母数 = 原序列的长度 — 原串和逆序的最长公共子串长度 , 如果最长公共子串长度==原序列长度，则是回文，反之须补充的数目为n-lcs；
这样做的原因如下：
要求最少添加几个字符，我们可以先从原串中找到一个最长回文串，然后对于原串中不属于这个回文串的字符，在它关于回文串中心的对称位置添加一个相同字符即可。那么需要添加的字符数量即为n-最长回文串长度。
最长回文串可以看作是原串中前面和后面字符的一种匹配（每个后面的字符在前面找到一个符合位置要求的与它相同的字符）。这种的回文匹配和原串与逆序串的公共子序列是一一对应的（一个回文匹配对应一个公共子序列，反之亦然），而且两者所涉及到的原串中的字符数量是相等的，也就是最长公共子序列对应最长回文串。原因陈述完毕。
代码：
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include <math.h>#define inf 0x3f3f3f3ftypedef int ll;#define N 1010using namespace std;char a[5010],b[5010];short int c[5010][5010];int main(){ int n; while(scanf("%d",&n)!=EOF) { scanf("%s",a); for(int i=n-1; i>=0; i--) b[n-1-i]=a[i]; for(int i=0; i<n; i++) { c[i][0]=0; c[0][i]=0; } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(a[i-1]==b[j-1]) { c[i][j]=c[i-1][j-1]+1; } else { c[i][j]=max(c[i-1][j],c[i][j-1]); } } } printf("%d\n",n-c[n][n]); } return 0;}
POJ159:Palindrome(LCS小应用 回文）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。