Read two strings and print the length of their longest common subsequence (LCS) and one LCS.
Fill the table dp[i][j] = LCS length of the first i characters of x and the first j characters of y. Then rebuild one LCS by walking back from dp[m][n] with this exact rule, so that the output is deterministic:
- If
x.charAt(i - 1) == y.charAt(j - 1), the character belongs to the LCS: record it and move to (i − 1, j − 1). - Otherwise, if
dp[i - 1][j] >= dp[i][j - 1], move up to (i − 1, j). - Otherwise move left to (i, j − 1).
Stop when i or j reaches 0; the recorded characters, reversed, are the LCS.
Input. Two lines, each holding one string (it may be empty; characters are compared exactly, case-sensitively). Lengths are at most 2 000.
Output. Two lines:
Length: L
LCS: S
(for an empty LCS, the second line is LCS: followed by nothing).
Example.
Input:
PROGRAM
GRAMMAR
Output:
Length: 4
LCS: GRAM