Longest Common Subsequence Length

You are given two strings representing protein sequences. Your task is to compute the length of the Longest Common Subsequence (LCS) between these two sequences.

The LCS problem is defined as follows: Given two sequences (s_1) and (s_2), find the length of the longest sequence which is a subsequence of both (s_1) and (s_2). A subsequence is obtained by deleting some or no elements without changing the order of the remaining elements.

The recurrence relation for computing the LCS is given by:
[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } s_1[i-1] = s_2[j-1] \ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases} ]
Implement an efficient algorithm to solve this problem.

inputFormat

The input consists of two lines. The first line contains the first protein sequence (a string), and the second line contains the second protein sequence (a string).

outputFormat

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

AACCTTGG
ACACTGTGA

6