Longest common subsequence

Problem

A subsequence keeps letters in order but may skip some. Find the length of the longest subsequence that two words share, using a cached recursion.

Example

Input

abcde
ace

Output

The shared subsequence is ace.

Try the problem first. Open one hint at a time.

Hint 1

Compare the first letters. If they match, the answer is 1 plus the answer for both tails.

Hint 2

If not, take the better of dropping a letter from one word or the other.

Write your Python code, run it on the examples and submit it to hidden tests.