Longest Common Subsequence

Lab Python Advanced 30 points

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

Input

Two lines.

Output

One integer.

Example

Input

ABCBDAB
BDCABA

Output

Sample input available Sample output available

Editor

Python

Hints

Build a table where dp[i][j] is the answer for the first i and j characters.

Solution explanation

2D DP tables are a common pattern for comparing two sequences (diff tools use similar ideas).

Show solution

a = input()
b = input()
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[-1][-1])

Output

Answer