题目

给定一个字符串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