poj 1458 Common Subsequence

Description

Input

Output

Sample Input

abcfbc         abfcab
programming    contest 
abcd           mnp

Sample Output

4
2
0

题意：求最长公共子序列；

解题思路：

求最长公共子序列（LCS）：

字符串：s:  S1S2S3S4.......Si，t:   T1T2T3T4..........Tj；

定义一个数组dp[i][j]表示S1S2S3S4.......Si和T1T2T3T4..........Tj所对应的最长公共子序列；

则S1S2S3S4.......Si+1和T1T2T3T4..........Tj+1所对应的最长公共子序列可能为：

（1）如果Si+1==Tj+1，则S1S2S3S4.......Si和T1T2T3T4..........Tj所对应的最长公共子序列+1；

（2）S1S2S3S4.......Si+1和T1T2T3T4..........Tj所对应的最长公共子序列；

（3）S1S2S3S4.......Si和T1T2T3T4..........Tj+1所对应的最长公共子序列；

所以dp的状态转移方程为dp[i][j]=max( dp[i-1][j-1] + (a[i]==b[j]) , max( dp[i-1][j] , dp[i][j-1] ) )

#include <iostream>
#include <string.h>
using namespace std;
char a[1000],b[1000];
int dp[1000][1000];
int max(int a,int b){
	return a>b?a:b;
}
int LCS(char *a,char *b){
	int n=strlen(a),m=strlen(b);
	for (int i=0;i<n;i++)
		dp[i][0]=0;
	for (int j=0;j<m;j++)
		dp[0][j]=0;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++){
			if (a[i]==b[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[n][m];
}
int main(){
	while (cin>>a>>b){
		cout<<LCS(a,b)<<endl;
	}
	return 0;
} 

poj 1458 Common Subsequence

原文：http://blog.csdn.net/codeforcer/article/details/40374647