Longest Common Subsequence

Given two strings, the task is to determine the length of their Longest Common Subsequence (LCS). The LCS is the longest sequence that appears in both strings in the same order, but not necessarily in a contiguous block.

You can use dynamic programming to solve this problem. The recurrence relation is given by:

$$ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] + 1, & \text{if } \text{text1}[i-1] = \text{text2}[j-1] \\ \max(\text{dp}[i-1][j],\text{dp}[i][j-1]), & \text{otherwise} \end{cases} $$

Your program should read two input strings from standard input and output the length of their LCS.

inputFormat

The input consists of two lines. The first line contains the first string (text1) and the second line contains the second string (text2).

outputFormat

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

abcde
ace

3