Longest common subsequence
Print the length of the longest sequence of characters that appears in both strings in the same order (not necessarily next to each other).
Reported in: LTIMindtree (memory-based)
Input
Two lines, one string each.
Output
The length.
Constraints
1 ≤ length ≤ 1000.
Example 1
Input:
ABCBDAB
BDCABA
Output:
4Example 2
Input:
abc
def
Output:
0Hint: dp[i][j] = dp[i−1][j−1] + 1 when the characters match, otherwise the larger of dp[i−1][j] and dp[i][j−1].