Longest Common Subsequence

Given two strings, compute the length of their longest common subsequence (LCS). A subsequence is a sequence which can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Formally, let (\text{text1}) and (\text{text2}) be two strings. Your task is to determine the length of the longest sequence (LCS) such that (LCS) is a subsequence of both (\text{text1}) and (\text{text2}).

For example, if (\text{text1} = \text{abcde}) and (\text{text2} = \text{ace}), the longest common subsequence is (\text{ace}) with a length of 3. Implement an efficient solution using dynamic programming.

inputFormat

The input consists of two lines:

1. The first line contains the string (\text{text1}).
2. The second line contains the string (\text{text2}).

Both strings may be empty and consist of lowercase letters.

outputFormat

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

abcde
ace

3