THINK FIRST·CODE LATER

← All labs

Longest common subsequence with reconstruction

Problem

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:

  1. If x.charAt(i - 1) == y.charAt(j - 1), the character belongs to the LCS: record it and move to (i − 1, j − 1).
  2. Otherwise, if dp[i - 1][j] >= dp[i][j - 1], move up to (i − 1, j).
  3. 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

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d8-2-data-1.txt

PROGRAM
GRAMMAR
What your program must print for d8-2-data-1.txt
Length: 4
LCS: GRAM

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d8-2-data-1.txt

Windows PowerShell does not understand <:

Get-Content d8-2-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.