9252 LCS 2

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <stack>
 
using namespace std;
 
string str1, str2;
int dp[1005][1005] = { 0 };
 
stack<int> rst;
 
int main() {
    cin >> str1 >> str2;
    
    int len1 = str1.size();    // i
    int len2 = str2.size(); // j
 
    str1 = "0" + str1;
    str2 = "0" + str2;
 
    for (int i = 1; i <= len2; i++) {
        if (str2[i] == str1[1]) {
            dp[1][i] = 1;
 
            for (int j = i; j <= len2; j++) {
                dp[1][j] = 1;
            }
        }
    }
 
    for (int i = 2; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i] == str2[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
 
    printf("%d\n", dp[len1][len2]);
 
    int tmp = dp[len1][len2];
    int idx = len2;    
    for (int i = len1; i >= 1; i--) {        
        if (tmp == 0)
            break;
 
        for (int j = idx; j >= 1; j--) {
            if (dp[i][j] == tmp && dp[i][j-1]!=tmp) {
                while (dp[i][j] == tmp) {
                    i--;
                }
                i++;
 
                rst.push(j);
                tmp -= 1;
                idx = j-1;                
                break;
            }
        }
    }
 
    while (rst.empty()==false) {
        int idx = rst.top();
        rst.pop();
        
        printf("%c", str2[idx]);
    }
 
}