Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is a classic problem in computer science. Given two strings, your task is to determine the length of the longest subsequence that is common to both strings. A subsequence is a sequence that can be derived from the original string by deleting some elements without changing the order of the remaining elements.

The dynamic programming approach to solve this problem is based on the following recurrence relation:

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

Your program should read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input consists of two lines:

The first line contains the first string, and the second line contains the second string. Both strings may be empty.

outputFormat

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

AGGTAB
GXTXAYB

4