本文共 1438 字，大约阅读时间需要 4 分钟。
第1行：字符串A第2行：字符串B(A,B的长度 <= 1000)
输出最长的子序列，如果有多个，随意输出1个。
abcicbaabdkscab
abca
#include #include #include #include #include #include #include #include #include #include #include #include //#include //#define LOACL#define space " "using namespace std;//typedef long long Long;//typedef __int64 Int;typedef pair paii;const int INF = 0x3f3f3f3f;const double ESP = 1e-6;const double PI = acos(-1.0);const int MOD = 1e9 + 7;const int MAXN = 1000 + 5;char str1[MAXN], str2[MAXN];int dp[MAXN][MAXN], vis[MAXN][MAXN];void print(int x, int y) { if (x == 0 || y == 0) return; if (vis[x][y] == 1) { print(x - 1, y - 1); printf("%c", str1[x - 1]); } else if (vis[x][y] == 2) { print(x - 1, y); } else { print(x, y - 1); }}int main() { while (scanf("%s%s", &str1, &str2) != EOF) { int cnt = 0, t = 0; int len1 = strlen(str1); int len2 = strlen(str2); memset(dp, 0, sizeof(dp)); memset(vis, 0, sizeof(vis)); for (int i = 1;i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; vis[i][j] = 1; } else if (dp[i - 1][j] > dp[i][j - 1]){ dp[i][j] = dp[i - 1][j]; vis[i][j] = 2; } else { dp[i][j] = dp[i][j - 1]; vis[i][j] = 3; } } } print(len1, len2); printf("\n"); } return 0;}
转载于:https://www.cnblogs.com/cniwoq/p/6770799.html