Longest Common Subsequence

Given two strings X and Y, your task is to compute the length of their longest common subsequence (LCS). The LCS of two strings is defined as the longest sequence that appears in both strings (not necessarily contiguous). For example, the LCS of AGGTAB and GXTXAYB is GTAB with a length of 4.

You can refer to the formula for computing the LCS length using dynamic programming as follows:

[ L(i,j)=\begin{cases} 0 & \text{if } i=0 \text{ or } j=0,\[6pt] L(i-1,j-1)+1 & \text{if } X_{i}=Y_{j},\[6pt] \max(L(i-1,j),L(i,j-1)) & \text{if } X_{i}\neq Y_{j}. \end{cases} ]

Note: The indices here are 1-indexed for explanation. In your implementation, adjust accordingly.

inputFormat

The input consists of two lines. The first line contains the string X, and the second line contains the string Y. Both strings may consist of uppercase English letters. They can also be empty.

outputFormat

Output a single integer representing the length of the longest common subsequence of the two given strings.

## sample

AGGTAB
GXTXAYB

4

</p>