Longest Common Subsequence

In this problem, you are given two strings s1 and s2. Your task is to compute the length of the longest common subsequence (LCS) between them.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Formally, if we denote the LCS length by \(LCS(s1,s2)\), then you need to compute the maximum \(k\) such that there exists indices \(i_1, i_2, \dots, i_k\) and \(j_1, j_2, \dots, j_k\) (with \(1 \le i_1 < i_2 < \dots < i_k \le |s1|\) and \(1 \le j_1 < j_2 < \dots < j_k \le |s2|\)) satisfying \(s1[i_l] = s2[j_l]\) for all \(l = 1, 2, \dots, k\).

One common approach to solve this problem is using dynamic programming. Let \(dp[i][j]\) denote the length of the LCS of the first \(i\) characters of s1 and the first \(j\) characters of s2. The recursive relation is given by:

\[ \begin{aligned} dp[i][j] &= dp[i-1][j-1] + 1 && \text{if } s1[i-1] = s2[j-1], \\ dp[i][j] &= \max(dp[i-1][j],\ dp[i][j-1]) && \text{if } s1[i-1] \neq s2[j-1]. \end{aligned} \]

The final answer will be \(dp[m][n]\), where \(m = |s1|\) and \(n = |s2|\).

inputFormat

The input consists of two lines:

1. The first line contains the string s1.
2. The second line contains the string s2.

You can assume that both strings contain only printable ASCII characters and do not have any spaces.

outputFormat

Output a single integer on a new line, which is the length of the longest common subsequence of s1 and s2.

## sample

abcde
ace

3

</p>