查找一个字符串的最长子序列的长度，该字符串是C ++中另一个字符串的子字符串

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

假设我们有两个字符串X和Y，我们必须找到字符串X的最长子序列的长度，它是序列Y中的子字符串。因此，如果X =“ ABCD”和Y =“ BACDBDCD”，则输出将为3因为“ ACD”是X的最长子序列，它是Y的子串。

在这里，我们将使用动态编程方法来解决此问题。因此，如果X的长度为n，Y的长度为m，则创建顺序为（m + 1）x（n + 1）的DP数组。DP [i，j]的值是X [0…j]的子序列的最大长度，它是Y [0…i]的子串。现在，对于DP的每个单元，如下所示：

  • 对于1到m范围内的i：

    • 当X [i – 1]与Y [j – i]相同时，则DP [i，j]：= 1 + DP [i – 1，j – 1]

    • 否则DP [i，j]：= 1 + DP [i，j – 1]

    • 对于1到n范围内的j

    最后，x的最长子序列（即y的子串）的长度为max（DP [i，n]），其中1 <= i <= m。

    示例

    #include<iostream>
    #define MAX 100
    using namespace std;
    int maxSubLength(string x, string y) {
       int table[MAX][MAX];
       int n = x.length();
       int m = y.length();
       for (int i = 0; i <= m; i++)
          for (int j = 0; j <= n; j++)
       table[i][j] = 0;
       for (int i = 1; i <= m; i++) {
          for (int j = 1; j <= n; j++) {
             if (x[j - 1] == y[i - 1])
                table[i][j] = 1 + table[i - 1][j - 1];
             else
                table[i][j] = table[i][j - 1];
          }
       }
       int ans = 0;
       for (int i = 1; i <= m; i++)
       ans = max(ans, table[i][n]);
       return ans;
    }
    int main() {
       string x = "ABCD";
       string y = "BACDBDCD";
       cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
    }

    输出结果

    Length of Maximum subsequence substring is: 3

    以上是 查找一个字符串的最长子序列的长度，该字符串是C ++中另一个字符串的子字符串 的全部内容， 来源链接： utcz.com/z/326998.html

    回到顶部