Problem B: Longest Common Subsequence

CS F364 — Assignment 1

← Back to assignment

Problem

A subsequence is obtained by deleting zero or more characters from a string (not necessarily contiguous) while preserving the relative order of the remaining characters. The longest common subsequence (LCS) of two strings \(A\) and \(B\) is the longest string that is a subsequence of both.

Given two strings \(A\) and \(B\), compute the length of their LCS and reconstruct one optimal LCS string.

Input Format

• Line 1: string \(A\) (length \(m\), \(1 \le m \le 5000\), lowercase a–z)
• Line 2: string \(B\) (length \(n\), \(1 \le n \le 5000\), lowercase a–z)

Output Format

• Line 1: integer — length of the LCS
• Line 2: the LCS string (one optimal solution)

Sample

Input

abcde
acbe

Output

3
ace

Explanation: LCS strings are “ace” and “abe” (both length 3). Either is acceptable.

Download sample input