Longest Common Subsequence

Given two strings s1 and s2, your task is to compute the length of their longest common subsequence (LCS). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

The problem can be formulated using dynamic programming. If we define a 2D array \(dp\) such that \(dp[i][j]\) represents the LCS length of the first \(i\) characters of \(s1\) and the first \(j\) characters of \(s2\), then the recurrence is:

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

Implement an efficient solution that reads from standard input and writes the result to standard output.

inputFormat

The input consists of two lines. The first line contains the string s1 and the second line contains the string s2.

outputFormat

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

abcde
ace

3