Dynamic ProgrammingString2D DP
Find the length of the longest subsequence that appears in both strings. A subsequence keeps the order of characters but may skip some.
Input
Line 1: the first string. Line 2: the second string. Both contain lowercase letters.
Output
Print the length of the longest common subsequence.
Constraints
1 <= length of each string <= 1000
Example 1
Input
abcde ace
Output
3
The common subsequence ace has length 3.
Example 2
Input
abc def
Output
0
Nothing in common.