Question
Research Notes Alignment
Two researchers typed notes about the same experiment, but both skipped some words while summarizing. Each note is represented as a lowercase string. A common trace is a sequence of characters that appears in both notes in the same relative order, not necessarily continuously.
Find the length of the longest common trace.
The twist: matching characters do not need to be adjacent, but their order must be preserved.
Input
The first line contains a string KaTeX can only parse string typed expression.
The second line contains a string KaTeX can only parse string typed expression.
Output
Print a single integer — the length of the longest common trace.
Example
Example 1:
Input
The sequence KaTeX can only parse string typed expression appears in both strings.
Example 2:
Input
Input
abcde
ace3The sequence KaTeX can only parse string typed expression appears in both strings.
Example 2:
Input
training
rating5