需要找到每个公共字符顺序相同的序列即可。
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
string s1;
string s2;
//数组保存
int maxLen[100][100];
int main(){
cout << "输入两个字符串,空格分开：";
while (cin >> s1 >> s2){
int len1 = s1.length();
int len2 = s2.length();
int n;
int i, j;
//初始化
for (i = 0; i <= len1; ++i)
maxLen[i][0] = 0;
for (j = 0; j <=len2; ++j)
maxLen[0][j] = 0;
for (i = 1; i <=len1; ++i)
{
for (j = 1; j <= len2; ++j)
{
if (s1[i - 1] == s2[j - 1])
maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
else{
maxLen[i][j] = max(maxLen[i - 1][j], maxLen[i][j - 1]);
}
}
}
cout << "最长子序列长度： "<<maxLen[len1][len2] << endl;
for (i = 0; i <= len1; ++i)
{
for (j = 0; j <= len2; ++j)
cout << " " << maxLen[i][j] << " ";
cout << endl;
}
}
return 0;
}
