查找C ++中最长公共子序列的长度的程序

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

假设我们有两个字符串text1和text2，我们必须找到它们最长的公共子序列的长度。众所周知，字符串的子序列是从原始字符串生成的新字符串，其中删除了一些字符，而不会更改其余字符的相对顺序。（因此，例如“ abe”是“ abcde”的子序列，而“ adc”则不是）。两个琴弦的共同子序列是两个琴弦共同的子序列。因此，如果没有公共子序列，则返回0。如果输入类似“ abcde”和“ ace”，则结果将为3。

为了解决这个问题，我们将遵循以下步骤-

  • n：= s的大小，m：= x的大小

  • 如果n为0或m为0，则返回0

  • s：=空字符串，与s串联

  • x：=空字符串，与x串联

  • ret：= 0

  • 定义阶数为（n + 1）x（m + 1）的矩阵dp

  • 对于我在1到n范围内

    • dp [i，j]：= dp [i，j-1]和dp [i – 1，j]的最大值

    • 如果s [i] = x [j]，则

    • dp [i，j]：= dp [i，j]的最大值，1 + dp [i – 1，j – 1]

    • 对于1到m范围内的j

    • 返回dp [n，m]

    让我们看下面的实现以更好地理解-

    示例

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
       public:
       int longestCommonSubsequence(string s, string x) {
          int n = s.size();
          int m = x.size();
          if(!n || !m) return 0;
          s = " " + s;
          x = " " + x;
          int ret = 0;
          vector < vector <int> > dp(n + 1, vector <int>(m + 1));
          for(int i = 1; i <= n; i++){
             for(int j = 1; j <= m ; j++){
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if(s[i] == x[j]) {
                   dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
                }
             }
          }
          return dp[n][m];
       }
    };
    main(){
       Solution ob;
       cout << (ob.longestCommonSubsequence("abcde", "ace"));
    }

    输入项

    "abcde"
    "ace"

    输出结果

    3

    以上是 查找C ++中最长公共子序列的长度的程序 的全部内容， 来源链接： utcz.com/z/345632.html

    回到顶部