poj1458--Common Subsequence--最长公共子序列LCS

本文主要是介绍poj1458--Common Subsequence--最长公共子序列LCS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最最基础的LCS问题～～～

关于LCS有很多很多的解释：

觉得这四个说的蛮好的：觉得这四个说的蛮好的：

http://blog.chinaunix.net/uid-26548237-id-3374211.html

http://blog.csdn.net/yysdsyl/article/details/4226630

http://blog.csdn.net/v_july_v/article/details/6695482

http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html

以下是我写的LCS代码，～

#include <cstdio>
#include <cstring>
using namespace std;
const int maxnum=1e4;char a[maxnum];
char b[maxnum];
int f[maxnum][maxnum];
int prin[maxnum][maxnum];//输出最长公共子序列
void dfs(int m,int n)
{if(m==0||n==0) return;if(prin[m][n]==0){dfs(m-1,n-1);//向左上走，只有两个字符相等的时候才输出printf("%c",a[m-1]);}else if(prin[m][n]==1){dfs(m-1,n);//向上走}else if(prin[m][n]==-1){dfs(m,n-1);//向左走}
}
int main()
{freopen("input.txt","r",stdin);while(scanf("%s%s",a,b)!=EOF){int m=strlen(a);int n=strlen(b);//Intializefor(int i=0; i<=m; ++i)f[0][i]=0;for(int i=1; i<=n; ++i)f[i][0]=0;//求最长公共子序列的长度for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){if(a[i-1]==b[j-1]){f[i][j]=f[i-1][j-1]+1;prin[i][j]=0;}else{if(f[i-1][j]>=f[i][j-1]){f[i][j]=f[i-1][j];prin[i][j]=1;}else{f[i][j]=f[i][j-1];prin[i][j]=-1;}}}}printf("%d\n",f[m][n]); //输出最长长度dfs(m,n);printf("\n");}return 0;
}

这篇关于poj1458--Common Subsequence--最长公共子序列LCS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---