Longest Common Subsequence

You are given two strings, A and B. 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 solution requires you to work with dynamic programming techniques. Note that the problem is case-sensitive.

Formula: If we denote dp[i][j] as the length of LCS of A[0..i-1] and B[0..j-1], then the recurrence is:

\(dp[i][j]=\begin{cases}0,&\text{if } i=0 \text{ or } j=0,\\ dp[i-1][j-1]+1,&\text{if } A[i-1]=B[j-1],\\ \max(dp[i-1][j], dp[i][j-1]),&\text{otherwise}.\end{cases}\)

inputFormat

The input consists of two lines:

• The first line contains string A.
• The second line contains string B.

outputFormat

Output a single integer, which is the length of the longest common subsequence of A and B.

ABCBDAB
BDCABC

4