数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中计算两个字符串的公共子序列
给定两个字符串，假设为 str1 和 str2，它们包含字符，任务是计算这两个字符串中的公共子序列。在下面的程序中，我们使用动态规划，为此我们需要了解什么是动态规划以及它可以用于哪些问题。
动态规划方法类似于分治法，它将问题分解成越来越小的子问题。但与分治法不同的是，这些子问题不是独立解决的。相反，这些较小子问题的结果会被记住并用于类似或重叠的子问题。
动态规划用于存在可以分解成类似子问题的问题，以便可以重用其结果。通常，这些算法用于优化。在解决手头的子问题之前，动态算法会尝试检查先前解决的子问题的结果。子问题的解决方案被组合起来以获得最佳解决方案。
所以我们可以说 -
Input − string str1 = “abc” String str2 = “ab” Output − count is 3
解释 - 从给定的字符串中形成的公共子序列为：{‘a’, ‘b’ , ‘ab’}。
Input − string str1 = “ajblqcpdz” String str2 = “aefcnbtdi” Output − count is 11
公共子序列是 - 从给定的字符串中形成的公共子序列为：{“a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ac”, “cd”, “abd”, “acd” }
下面程序中使用的步骤如下
输入两个字符串，假设为 str1 和 str2。
使用 length() 函数计算给定字符串的长度，该函数将根据字符串中的字符数返回一个整数值，并将其存储在 str1 的 len1 和 str2 的 len2 中。
创建一个二维数组来实现动态规划，假设为 arr[len1+1][len2+1]
开始循环，从 i=0 到 i 小于 len1
在循环内部，开始另一个循环，从 j=0 到 j 小于 len2
在循环内部，检查 IF str1[i-1] = str2[j-1]，然后设置 arr[i][j] = 1 + arr[i][j-1] + arr[i-1][j]
否则，则设置 arr[i][j] = arr[i][j-1] + arr[i-1][j] = arr[i-1][j-1]
返回 arr[len1][len2]
打印结果。
示例
#include <iostream>
using namespace std;
// To count the number of subsequences in the string
int countsequences(string str, string str2){
int n1 = str.length();
int n2 = str2.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++){
for (int j = 0; j <= n2; j++){
dp[i][j] = 0;
}
}
// for each character of str
for (int i = 1; i <= n1; i++){
// for each character in str2
for (int j = 1; j <= n2; j++){
// if character are same in both
// the string
if (str[i - 1] == str2[j - 1]){
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
}
else{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}
}
return dp[n1][n2];
}
int main(){
string str = "abcdejkil";
string str2 = "bcdfkaoenlp";
cout <<"count is: "<<countsequences(str, str2) << endl;
return 0;
}示例
如果我们运行上述代码，我们将得到以下输出 -
count is: 51
512 次查看
