Longest Common Subsequence for DNA Strands

Your task is to find the longest common subsequence (LCS) between two DNA strands. The LCS of two sequences is defined as the longest sequence that can be derived from both sequences by deleting some or no elements without changing the order of the remaining elements.

For example, given the two strands AGGTAB and GXTXAYB, the LCS is GTAB.

A common dynamic programming approach is used where the recurrence relation is given by $\displaystyle dp[i][j]=\begin{cases} dp[i-1][j-1]+1,&\text{if } s1[i-1]=s2[j-1]\\ \max(dp[i-1][j],dp[i][j-1]),&\text{otherwise} \end{cases}$.

Solve this problem using an efficient algorithm.

inputFormat

The input is read from stdin and consists of exactly two lines. The first line contains the first DNA strand and the second line contains the second DNA strand. Each strand is a non-empty string made up of the characters A, C, G, and T.

outputFormat

Output the longest common subsequence on stdout. If there is no common subsequence, output an empty string.## sample

AGGTAB
GXTXAYB

GTAB