LCS 7
Time limit2sMemory limit8 MB
Given two strings of length up to 50000, find the length of their longest common subsequence and print one such subsequence.
- Level
Hard8 of 10
- Topics
- String, Dynamic programming, Binary search, Divide and conquer
- Solved
- No attempts yet
Problem
The LCS (Longest Common Subsequence) problem asks, given two sequences, for the longest sequence that is a subsequence of both.
For example, the LCS of ACAYKP and CAPCAK is ACAK.
Input
The first and second lines each contain one string. A string consists only of uppercase English letters and has length at most 50000.
Output
On the first line, print the length of the LCS of the two given strings. On the second line, print the LCS itself.
If there are multiple LCSes, print any one of them.