Longest Common Subsequence

Problem statement

Two archivists transcribe related sequences of symbols. To measure their shared ordering, a reviewer seeks the longest sequence that can be recovered from both transcripts by deleting symbols without rearranging the survivors. Your task Find the length of the longest common subsequence of the two strings. Important details The matching symbols need not occupy adjacent positions. Their order must agree in both strings. Repeated symbols may be used only as often as matching positions permit. Return zero when there is no common symbol. Worked example For abcde and ace, the sequence ace appears in order in both strings. Its length is 3, which is the maximum.

Input format

Two lines containing the strings.

Output format

Print the longest common subsequence length.

Constraints

1 <= lengths <= 1000; lowercase English letters.

Sample input

abcde
ace

Sample output

3