计算C ++中两个字符串中的公共子序列

  • Z时代
  • 2024-01-10
  • 分类：综合

我们给了两个字符串，假设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]

  • 从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;
//计算字符串中的子序列数
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;
      }
   }
   //对于str的每个字符
   for (int i = 1; i <= n1; i++){
      //对于str2中的每个字符
      for (int j = 1; j <= n2; j++){
         //如果两个字符都相同
         //字符串
         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

以上是 计算C ++中两个字符串中的公共子序列 的全部内容， 来源链接： utcz.com/z/324977.html

回到顶部