Q:有两个序列x，y。其中x={x1,x2…xm}，y={y1,y2…yn}。寻找x与y的最长公共子序列。
注：子序列和子串有区别，字串是连续的，而子序列可间断。
呃(⊙﹏⊙)，后面的暂时没时间写了，先挂代码吧……
#include <iostream>#include<string>#include<vector>using namespace std;struct TLCS{int l;//表示该点代表的问题的最长子序列的长char from;//左：'l'，上：'u'，左上：'e'TLCS() :l(0) {}//初始化l为0};int main(){string s1, s2;cin >> s1;cin >> s2;int m = s1.size();int n = s2.length();char* x = new char[m + 1];//x[1]~x[m]用于存储x1~xm，x[0]不用char* y = new char[n + 1];//y同理，y[0]空着//通过字符串赋值for (int i1 = 1; i1 < m + 1; i1++)x[i1] = s1.at(i1 - 1);for (int j1 = 1; j1 < n + 1; j1++)y[j1] = s2.at(j1 - 1);TLCS** LCS = new TLCS * [m + 1];for (int k = 0; k <= m ; k++)LCS[k] = new TLCS[n + 1];for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (x[i] == y[j]){LCS[i][j].l = LCS[i - 1][j - 1].l + 1;LCS[i][j].from = 'e';}else{int l1 = LCS[i][j - 1].l;int l2 = LCS[i - 1][j].l;if (l1 > l2){LCS[i][j].l = l1;LCS[i][j].from = 'l';}else{LCS[i][j].l = l2;LCS[i][j].from = 'u';}}}}//构造解：将最长公共子序列放入一个向量vector<char> v;int i2 = m; int j2 = n;while (i2 > 0 && j2 > 0){switch (LCS[i2][j2].from){case'e':v.push_back(x[i2]); i2--; j2--; break;case'l':j2--; break;default:i2--; break;}}//打印最长公共子序列(向量反向）for (int i3 = v.size() - 1; i3 >= 0; i3--)cout << v[i3];//释放内存for (int i4 = 0; i4 <= m; i4++)delete[] LCS[i4];delete[] LCS;delete[] x;delete[] y;return 0;}
如果有看不明白或者好的建议，欢迎探讨。
如果帮到你了，点赞评论鼓励下萌新吧~贴贴
