Longest Common Subsequence

Given two strings s₁ and s₂, find the length of their longest common subsequence (LCS). A subsequence is a sequence that appears in the same relative order in both strings, but not necessarily contiguously. For example, "ace" is a subsequence of "abcde", and its length is 3.

Let ( dp[i][j] ) denote the length of the LCS of the first ( i ) characters of s₁ and the first ( j ) characters of s₂. The recurrence relation is given by:
[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } s₁[i-1] = s₂[j-1] \ \max(dp[i-1][j], dp[i][j-1]), & \text{otherwise} \end{cases} ]

Your task is to implement an efficient solution using dynamic programming to compute the length of the longest common subsequence between the two provided strings.

inputFormat

The input consists of two lines read from STDIN. The first line contains the first string (s₁) and the second line contains the second string (s₂). Both strings contain only lowercase English letters.

outputFormat

Output a single integer to STDOUT representing the length of the longest common subsequence between the two strings.## sample

abcde
ace

3