最长公共子序列运用

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。 思路：将原字符串反转，求出元字符串与反转字符串最长公共子序列(也就是最长的回文串); c++代码(网上搜的)：

点击(此处)折叠或打开

#include <bits/stdc++.h> using namespace std; const int MAXN=1010; int dp[MAXN][MAXN]; class Solution { public:    int solve(string &s)    {        return s.length()-getLCS(s);    }    int getLCS(string &s1)    {        string s2(s1);        reverse(s2.begin(),s2.end());        int len=s1.length();        memset(dp,0,sizeof dp);        for(int i=0;i<len;++i)        {            for(int j=0;j<len;++j)            {                if(s1[i]==s2[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]);            }        }        return dp[len][len];    } }; int main() {    string s;    while(cin>>s)    {        Solution solution;        cout<<solution.solve(s)<<endl;    }    return 0; } c语言代码：

点击(此处)折叠或打开

#include<stdio.h> #include<stdlib.h> #include<string.h> void reverse(char *str,int from,int to) {     while (from < to)     {         char temp = str[from];         str[from++] = str[to];         str[to--] = temp;     } } int getLcs(char *str1,char *str2,int length) {     //printf("%s %s\n",str1,str2);//居然是一样的     int dp[length][length];     int i =0,j = 0;     for (i = 0;i <length;i++)     {         for (j = 0;j < length;j++)             dp[i][j] = 0;     } //    int i = 0,j = 0;     for (i = 0;i < length;i++)     {         for (j = 0;j < length;j++)         {             if (i == 0 || j == 0)             {                 if (str1[i] == str2[j])                 {                     dp[i][j] = 1;                 }                 else                 {                     if (i > 0)                         dp[i][j] = dp[i-1][j];                     if (j > 0)                         dp[i][j] = dp[i][j-1];                 }             }             else if (str1[i] == str2[j])             {                 dp[i][j] = dp[i-1][j-1]+1;             }             else {                 dp[i][j] = ((dp[i-1][j] > dp[i][j-1]) ?dp[i-1][j]:dp[i][j-1]);             }         }     }     return dp[length-1][length-1]; } int main() {     char str[1024];//注意下字符串指针     //char *str1 = "abcda";     //char *str2 = "adcba";          while (gets(str))     {         int len = strlen(str);         char str1[1024];     //    char *str1 = str;     //    printf("str1 = %s\n",str1);                  strcpy(str1,str);         reverse(str,0,len-1);                  //printf("str2 = %s\n",str2);         int result = getLcs(str1,str,len);         printf("%d\n",(len-result));         //free(str2);     }     return 0;     //getLcs()      } <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script> 阅读(687) | 评论(0) | 转发(0) | 0

上一篇：字符串反转

下一篇：[cisco]用宏定义写出swap（x，y）

相关热门文章 test123编写安全代码——小心有符号数...使用openssl api进行加密解密...一段自己打印自己的c程序...彻底搞定C语言指针详解-完整版... 给主人留下些什么吧！~~ 评论热议