最长公共子序列
程序员文章站
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;
}
上一篇: P1042 乒乓球---题解
下一篇: 265. 粉刷房子 II