BOJ. LCS 2 (9252)

Problem

Let dp[i][j] be the length of the longest common subsequence of the first i characters of a and the first j characters of b. An empty prefix has LCS length zero. If the last characters match, they can extend an LCS of the two preceding prefixes; otherwise an LCS must omit at least one of those last characters:

dp[0][j] = dp[i][0] = 0

dp[i][j] = dp[i - 1][j - 1] + 1                         if a[i - 1] == b[j - 1]
           max(dp[i - 1][j], dp[i][j - 1])              otherwise

Fill the table from smaller prefixes to larger ones. To recover one LCS, walk backward from (n, m): on a matching pair, record that character and move diagonally; otherwise move to a neighboring cell with the same LCS length. The table invariant guarantees that each diagonal match contributes one character and each non-diagonal move preserves the best attainable length. Reversing the recorded characters gives an LCS of length dp[n][m]. When lengths tie either neighbor is valid, so repeated characters are handled without requiring a unique answer. The algorithm takes O(NM) time and O(NM) space. It prints the length followed by one LCS line; if the length is zero, that second line is blank.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String a = input.readLine();
        String b = input.readLine();
        int n = a.length();
        int m = b.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder reversed = new StringBuilder();
        int i = n;
        int j = m;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                reversed.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        System.out.println(dp[n][m]);
        System.out.println(reversed.reverse());
    }
}