Longest Common Subsequence

Given two strings str1 and str2, compute the length of their Longest Common Subsequence (LCS). A subsequence is a sequence that appears in the same relative order, but not necessarily contiguously. For example, "abc", "abg", "bdf", "aeg", and "acefg" are all subsequences of "abcdefg".

The task is to determine the length of the longest sequence which is a subsequence of both given strings. The solution should implement the dynamic programming approach to solve the problem efficiently.

The relationship in the dynamic programming solution can be expressed as: $$ \text{dp}[i][j]=\begin{cases} \text{dp}[i-1][j-1]+1 & \text{if }str1[i-1]=str2[j-1]\\ \max(\text{dp}[i-1][j],\text{dp}[i][j-1]) & \text{otherwise} \end{cases} $$ where \(dp[i][j]\) represents the length of the LCS of the first \(i\) characters of str1 and the first \(j\) characters of str2.

inputFormat

The input is read from stdin and consists of exactly two lines. The first line contains the string str1 and the second line contains the string str2.

It is guaranteed that the strings may be empty and consist only of printable ASCII characters.

outputFormat

The output is a single integer written to stdout which represents the length of the longest common subsequence between the two strings.

## sample

abcde
ace

3

</p>