当前位置:首页>>最长公共子序列

最长公共子序列

给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB

则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列

//方法一:动态规划思想
#include <iostream>
#include <string.h>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int LCS(char a[],char b[]){
    //最长公共子序列
    int len_a = strlen(a), len_b = strlen(b);
    int dp[100][100];
    for (int i = 1; i < len_a; ++i) {
        for (int j = 1; j < len_b; ++j) {
            if(a[i]==b[j])
                dp[i][j] = dp[i-1][j-1] +1;
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[len_a-1][len_b-1];
}
int main(){
    char a[100],b[100];
    cin >> a+1 >> b+1;
    //将 a数组和 b数组向后移动一个位置
    cout << LCS(a,b) << endl;
    return 0;
}
//方法二:递归解法
#include <iostream>
#include <string.h>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int LCS(char a[],int n,char b[],int m){
    if(n==strlen(a)||m==strlen(b))
        return 0;
    else if(a[n]==b[m])
        return LCS(a,n+1,b,m+1) + 1;
    else
        return max(LCS(a,n+1,b,m),LCS(a,n,b,m+1));
}
int main(){
    char a[100],b[100];
    cin >> a >> b;
    cout << LCS(a,0,b,0) << endl;
    return 0;
}

猜你喜欢