Longest Common Subsequence

Given two strings, find the length of their Longest Common Subsequence (LCS).

The LCS of two strings is defined as the longest sequence that appears in both strings in the same relative order, but not necessarily contiguously.

You can solve this using dynamic programming. The recurrence relation is as follows:

$$ \text{dp}[i][j]=\begin{cases} \text{dp}[i-1][j-1]+1, &\text{if } s_1[i-1]=s_2[j-1]\\ \max(\text{dp}[i-1][j],\text{dp}[i][j-1]), &\text{otherwise} \end{cases} $$

Here, \(s_1\) and \(s_2\) denote the two input strings. The final answer is \(\text{dp}[m][n]\), where \(m\) and \(n\) are the lengths of the two strings respectively.

inputFormat

The input consists of two lines. The first line contains the first string, and the second line contains the second string.

outputFormat

Output a single integer which is the length of the longest common subsequence of the two input strings.## sample

ABCBDAB
BDCAB

4