A subsequence is a sequence derived from an another original sequence by deleting some elements while leaving the order unchanged.
Given 2 strings, find the length of the longest common subsequence between them. There will be no spaces in the strings and it would be less than 1000 characters long.
Input
2 strings, one on each line
Output
A single integer indicating the length of the longest common subsequence.
Sample Input 1
happy
apple
Sample Output
3 [app is common]
Sample Input 2
Ranald
Iran
Sample Output 2
2 [an is common, R and r are not considered the same]