Challenge: Longest Common Subsequence

Lab Python Intermediate 20 points

Read two words and print the length of their longest common subsequence.

Input

Two lines, one word each (at most 200 letters).

Output

One number.

Example

Input

abcde
ace

Output

Sample input available Sample output available

Editor

Python

Hints

dp[i][j] uses the first i letters of a and the first j of b.

Matching letters: dp[i-1][j-1] + 1. Otherwise: max(dp[i-1][j], dp[i][j-1]).

Solution explanation

Each cell is filled once from three neighbours: O(n × m).

Show solution

a = input().strip()
b = input().strip()
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[len(a)][len(b)])

Output

Answer