# Appreciation

/*
 * Problem :: 9252 / LCS 2
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - LCS = Longest Common Substring
 *   + 문자열 u 와 v 가 주어졌을 때
 *     dp[i][j] = 문자열 u 의 i번째 글자까지와 문자열 v 의 j번째 글자까지 살펴보았을 때
 *                max(len(LCS))
 *     # if (u[i] == v[j]) <= 문자열 u 의 i번째 글자와 v 의 j번째 글자가 같다면
 *           dp[i][j] = dp[i-1][j-1] + 1
 *       else
 *           dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 *       -> u = "ACAYKP"
 *          v = "CAPCAK" 가 입력으로 주어졌을 때
 *          dp 는 아래와 같다
 *              ' ' C A P C A K
 *          ' '   0 0 0 0 0 0 0
 *          A     0 0 1 1 1 1 1
 *          C     0 1 1 1 2 2 2
 *          A     0 1 2 2 2 3 3
 *          Y     0 1 2 2 2 3 3
 *          K     0 1 2 2 2 3 4
 *          P     0 1 2 3 3 3 4
 *
 * - u = "ABCD"
 *   v = "DCBA" 가 입력으로 주어졌을 때
 *   dp 는 아래와 같다
 *       ' ' D C B A
 *   ' '   0 0 0 0 0
 *   A     0 0 0 0 1
 *   B     0 0 0 1 1
 *   C     0 0 1 1 1
 *   D     0 1 1 1 1
 *   + 이제 위의 dp 를 이용해서 LCS 를 구해야한다
 *     이는, 각 dp[i][j] 에서 어떤 조건의 점화식이 쓰였는지를 역추적하는 것과 같다
 *     #   C B
 *       A 0 0
 *       B 0 1
 *       여기서는 dp[2][3] = dp[1][2] + 1 임을 알 수 있고
 *       LCS 에 B 가 추가되었음을 뜻한다
 *     #   B A
 *       C 1 1
 *       D 1 1
 *       그렇다면 dp[4][4] 는 어떻게 역추적을 해야할까?
 *       이 경우에는 max(dp[i-1][j], dp[i][j-1]) 조건의 점화식이 쓰였는데
 *       dp[i-1][j] 와 dp[i][j-1] 의 값이 같다
 *       -> dp[i][j] = max(len(LCS)) 이므로
 *          이는 dp[i][j] 의 LCS 가 dp[i-1][j] 의 LCS 가 되어도
 *          또 dp[i][j] 의 LCS 가 dp[i][j-1] 의 LCS 가 될 수 있다는 것이다
 *          이는 중복의 해가 가능하다는 것을 뜻하는 것이다! <= LCS 는 여러가지 일 수 있다!
 *       -> 때문에 dp[4][4] = dp[3][4] 로 보아 위의 방향으로 역추적을 할 수도,
 *          또는 dp[4][4] = dp[4][3] 으로 보아 아래의 방향으로 역추적을 할 수도 있다
 *     #   C B
 *       B 0 1
 *       D 1 1
 *       이 dp[3][3] 의 경우는 어떡해야 할까?
 *       이 경우에는 dp[3][3] = dp[2][2] + 1 이긴 하지만 글자가 서로 다름을 알 수 있다
 *       즉, dp[3][3] = dp[2][3] 또는 dp[3][3] = dp[3][2] 로 볼 수 있으며
 *       마찬가지로 중복의 해가 가능함을 뜻하는 것이다
 *
 * - 위의 설명을 바탕으로 dp 를 통해 LCS 를 추적하는 방법은 다음과 같음을 알 수 있다
 *   + 문자열 u 와 v 가 주어졌을 때
 *     각 문자열의 길이를 lu = len(u), lv = len(v) 라고 하자
 *     dp[lu][lv] 를 시작점으로 LCS 를 추적한다
 *     그리고 현재 추적의 중간상태인 dp[i][j] 에 있다고 가정하자
 *     # dp[i][j] == dp[i-1][j] 또는 dp[i][j] == dp[i-1][j] 이면
 *       max(dp[i-1][j], dp[i][j-1]) 조건의 점화식이 사용되었으므로
 *       dp[i][j] 와 같은 값을 가지는 dp[i-1][j] 또는 dp[i][j-1] 로 이동하여
 *       추적을 계속 진행한다
 *       -> 만약 dp[i-1][j] 와 dp[i][j-1] 의 값이 같다면
 *          둘 중 어느쪽으로 이동해도 상관없다
 *          같은 길이의 서로다른 LCS 가 가능하다는 것을 뜻하기 때문이다
 *          (참고로 이 두 LCS 는 같거나 다를 수 있다)
 *     # 만약 dp[i][j] != dp[i-1][j] 이고 dp[i][j] != dp[i][j-1] 이면
 *       dp[i][j] = dp[i-1][j-1] + 1 조건의 점화식이 사용되었으므로
 *       dp[i-1][j-1] 의 LCS 에
 *       문자열 u 의 i번째 글자(또는 문자열 v 의 j번째 글자)가 추가된 것이다
 *       LCS 에 글자를 추가하고 dp[i-1][j-1] 로 이동하여 추적을 계속한다
 *
 * Point
 * - dp[i][j] 를 구할 때
 *   dp[i][j-1], dp[i-1][j] >= dp[i-1][j-1] 이고
 *   + max(dp[i][j-1] - dp[i-1][j-1]) = 1
 *     max(dp[i-1][j] - dp[i-1][j-1]) = 1 이므로
 *     # 따라서, 항상 (dp[i-1][j-1] + 1) >= dp[i-1][j], dp[i][j-1] 이다
 *
 * - dp 로부터 LCS 를 추적할 때
 *   LCS 에 가장 나중에 추가된 글자부터 만나게 된다
 *   + 문자열 lcs 가 있고 이 글자들을 만나는 순서대로 lcs.push_back(글자) 해주었다면
 *     lcs 뒤집어주어야 올바른 LCS 를 구할 수 있다
 *   + 코드에서는 뒤집어주기 귀찮아서 lcs.insert(lcs.begin(), 글자) 해주었다
 *     # reverse(lcs.begin(), lcs.end()) 만 해주면 되는데 귀찮아...?
 *
 * - dp 를 구할 때는
 *   + if (u[i] == v[j])
 *         dp[i][j] = dp[i-1][j-1] + 1
 *     else
 *         dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 *   dp 를 역추적 할 때는
 *   + if (dp[i][j] == dp[i-1][j] || dp[i][j] == dp[i][j-1])
 *         i--; or j--;
 *     else
 *         LCS.push_front(u[i] or v[j])
 *         i--; j--;
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source


#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string u; cin >> u;
    string v; cin >> v;

    // Process
    int lu = u.length();
    int lv = v.length();
    int dp[lu+1][lv+1];
    memset(dp, 0, sizeof(dp));

    /* dp 를 구함 */
    for (int i=1; i<=lu; i++) {
        char cu = u[i-1]; /* 문자열 u 의 i 번째 글자 */
        for (int j=1; j<=lv; j++) {
            char cv = v[j-1]; /* 문자열 v 의 i 번째 글자 */
            if (cu == cv) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    /* dp 를 역추적해서 LCS 를 구함 */
    string LCS;
    int y = lu, x = lv;
    while (y > 0 && x > 0) {
        /* 문자열 u 의 y 번째 글자와 문자열 v 의 x 번째 글자까지의 LCS 가
         * 문자열 u 의 y-1 번째 글자와 문자열 v 의 x 번째 글자까지의 LCS 와 같음 */
        if (dp[y][x] == dp[y-1][x])
            y--;
        /* 문자열 u 의 y 번째 글자와 문자열 v 의 x 번째 글자까지의 LCS 가
         * 문자열 u 의 y 번째 글자와 문자열 v 의 x-1 번째 글자까지의 LCS 와 같음 */
        else if (dp[y][x] == dp[y][x-1])
            x--;
        /* 문자열 u 의 y 번째 글자와 문자열 v 의 x 번째 글자까지의 LCS 가
         * 문자열 u 의 y-1 번째 글자와 문자열 v 의 x-1 번째 글자까지의 LCS 뒤에
         * 문자열 u 의 y 번째 글자(문자열 v 의 x 번째 글자) 를 더한 것과 같음 */
        else {
            LCS.insert(LCS.begin(), u[y-1]);
            y--; x--;
        }
    }

    // Control : Output
    cout << dp[lu][lv] << endl;
    cout << LCS << endl;
}

// Helper Functions
/* None */