查找一个字符串的最长子序列的长度，该字符串是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