欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长公共子序列

程序员文章站 2022-07-16 11:45:30
...

给定两个字符串,求解这两个字符串的最长公共子序列(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;
}
相关标签: 动态规划