题目
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子:
abcda
google
输出例子:
2
2
解题之法
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxsize=1010;
int temp[maxsize][maxsize];
int get_delete_number(string &s1){
string s2(s1);
reverse(s2.begin(),s2.end());//字符串反转
//反转函数之后求最长公共子序列
int len=s1.length();
memset(temp,0,sizeof temp);//对定义的字符串进行初始化
for(int i=0;i<len;i++)
for(int j=0;j<len;j++){//求最长公共子序列的方法
if(s1[i]==s2[j])
temp[i+1][j+1]=temp[i][j]+1;
else
temp[i+1][j+1]=max(temp[i][j+1],temp[i+1][j]);
}
return len-temp[len][len];
}
int main(){
string s;
while(getline(cin,s)){
cout<<get_delete_number(s)<<endl;
}
}
分析
一种可以参考的方法是先将字符串取反，然后再将反字符串和原字符串一起找最长公共子序列，最后就得到了最长的回文字符串，最后再加减长度就行了。
最长公共子序列可以不连续，最长公共子串则必须得连续。
本篇博客内容转载自[《构造回文串》][0]
[0]: http://www.voidcn.com/blog/half_open/article/p-6248147.html
