Common Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 34218 Accepted Submission(s): 15598
Problem Description A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X =
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define M 10010 int map[2][M]; int main() { char s1[M], s2[M]; while(scanf("%s%s", s1+1, s2+1) != EOF) { int n = strlen(s1+1); int m = strlen(s2+1); memset(map, 0, sizeof(map)); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(s1[i] == s2[j]) { map[i%2][j] = map[(i-1)%2][j-1] + 1; } else { map[i%2][j] = max(map[(i-1)%2][j], map[i%2][j-1]); } } } printf("%d\n", map[n%2][m]); } return 0; }顺便把这个回溯输出子序列也给摸出来了
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define M 10010 int map[2][M]; int main() { char s1[M], s2[M]; while(scanf("%s%s", s1+1, s2+1) != EOF) { int n = strlen(s1+1); int m = strlen(s2+1); memset(map, 0, sizeof(map)); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(s1[i] == s2[j]) { map[i%2][j] = map[(i-1)%2][j-1] + 1; } else { map[i%2][j] = max(map[(i-1)%2][j], map[i%2][j-1]); } } } int maxs = map[n%2][m]; int k = 0, a[M]; while(maxs != 0) { if(map[(n-1)%2][m-1] < maxs) { a[k++] = s2[m]; maxs--, n--, m--; } else { m--; } } for(int i=k-1; i>=0; i--) printf("%c ", a[i]); printf("\n"); } return 0; }