LCS:设d(i,j)为A1,A2,...,Ai和B1,B2,...,Bj的LCS长度,则当A[i]=B[j]时,d(i,j)=d(i-1,j-1)+1,否则d(i,j)=max{d(i-1,j),d(i,j-1)},时间复杂度为O(nm),其中n和m分别是A和B的长度。
输出LCS的思想其实就是倒过来反向推理的过程。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3+7; int a[maxn]; int b[maxn]; int dp[maxn][maxn]; int n, m; void printLCS() { vector<int> vec; int i = n, j = m; while(i > 0 && j > 0) { if(a[i] == b[j]) { vec.push_back(a[i]); i--; j--; } else { if(dp[i-1][j] > dp[i][j-1]) i--; else j--; } } printf("YES\n"); printf("%d ",dp[n][m]); for(int i = vec.size()-1; i >= 0; i--) { printf("%d ",vec[i]); } printf("\n"); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } for(int i = 1; i <= m; i++) { scanf("%d",&b[i]); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1; else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } if(dp[n][m] == 0) printf("NO\n"); else printLCS(); } }