Longest Common Subsequence

You are given two strings. Your task is to compute the length of the longest common subsequence (LCS) shared between them.

A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

The solution should implement the standard dynamic programming approach. The recurrence relation used is:

\[ dp[i][j]=\begin{cases} 0 & i=0 \text{ or } j=0, \\ dp[i-1][j-1]+1 & X[i-1]=Y[j-1], \\ \max\{dp[i-1][j],\ dp[i][j-1]\} & \text{otherwise.} \end{cases} \]

For example, given X = "ABCBDAB" and Y = "BDCABA", the length of the LCS is 4.

inputFormat

The input consists of exactly two lines:

• The first line contains the string X.
• The second line contains the string Y.

Each string can contain uppercase and lowercase English letters.

outputFormat

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

## sample

ABCBDAB
BDCABA

4