Description
Find a longest common subsequence of two strings.
Input: Strings s and t.
Output: A longest common subsequence of s and t.
A string is a subsequence of a string s if it can be obtained by deleting some symbols from s.
For example, GC and GAT are both subsequences of GACT.
A string x is a common subsequence of strings s and t if it is a subsequence of both s and t.
For example, G and AT are both common subsequences of GACT and ATG.
Our goal is to find a longest common subsequence (LCS) of 2 strings. Note that 2 strings may have more than one longest common subsequence.
Input Format.
The 1st. line of the input contains a string s,
The 2nd. line of the input contains a string t.
Output Format.
A longest common subsequence of s and t.
(Note: you can output any of the solutions.)
Constraints. |s| ≤ 1,000; |t| ≤ 1,000