最长公共子序列

题目描述

给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=是序列X=的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？

输入描述

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。

输出描述

对于每组输入，输出两个字符串的最长公共子序列的长度。

输入示例

abcfbc abfcab
programming contest 
abcd mnp

输出示例

4
2
0

Java 代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {String str1 = scanner.next();String str2 = scanner.next();System.out.println(lcs(str1, str2));}scanner.close();}// 动态规划解决最长公共子序列问题private static int lcs(String str1, String str2) {int m = str1.length();int n = str2.length();int[][] dp = new int[m+1][n+1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else if (str1.charAt(i-1) == str2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[m][n];}
}

C++ 代码

#include<iostream>
#include<vector>using namespace std;int f[110][110]; //到i，j有多少相同的元素int main(){string x; string y;while(cin>>x>>y){for(int i=1;i<=x.size();i++){for(int j=1;j<=y.size();j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(x[i-1]==y[j-1]) f[i][j]=max(f[i-1][j-1]+1,f[i][j]);}}cout<< f[x.size()][y.size()]<<endl;}
}