題目描述

給你一個序列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;
    }
}