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

假设我们有两个字符串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