Longest Common Subsequence using Recursive Memoization

Given two strings, the task is to determine the length of their longest common subsequence (LCS) using a recursive algorithm with memoization. The LCS of two strings is defined as the longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively.

The recurrence relation for LCS is given by:

$$ LCS(i,j)=\begin{cases} 0, & \text{if } i=0 \text{ or } j=0\\ 1+LCS(i-1,j-1), & \text{if } s_1[i]=s_2[j] \\ \max(LCS(i-1,j),LCS(i,j-1)), & \text{otherwise} \end{cases} $$

Your program should read input from standard input and output the result to standard output.

inputFormat

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

outputFormat

Output a single integer, the length of the longest common subsequence (LCS) of the two input strings.## sample

AGGTAB
GXTXAYB

4