Longest Common Subsequence

Background

Special for beginners, ^_^

Problem Description

A subsequence of a given sequence is a sequence obtained by deleting some elements from the given sequence.

More precisely, given a sequence $X = <x_1, x_2, \dots, x_m>$, another sequence $Z = <z_1, z_2, \dots, z_k>$ is a subsequence of $X$ if there exists a strictly increasing sequence of indices $<i_1, i_2, \dots, i_k>$ such that for all $j = 1, 2, \dots, k$:

$X_{i_j} = Z_j$

For example, the sequence $Z = <B,C,D,B>$ is a subsequence of $X = <A,B,C,B,D,A,B>$, with the corresponding increasing index sequence $<2,3,5,7>$.

Given two sequences $X$ and $Y$, when another sequence $Z$ is a subsequence of both $X$ and $Y$, we call $Z$ a common subsequence of $X$ and $Y$.

For example, if $X = <A,B,C,B,D,A,B>$ and $Y = <B,D,C,A,B,A>$, then the sequence $<B,C,A>$ is a common subsequence of $X$ and $Y$, and the sequence $<B,C,B,A>$ is also a common subsequence of $X$ and $Y$. Moreover, the latter is a longest common subsequence of $X$ and $Y$, because $X$ and $Y$ have no common subsequence longer than 4.

Given two sequences $X = <x_1, x_2, \dots, x_m>$ and $Y = <y_1, y_2, \dots, y_n>$, find a longest common subsequence of $X$ and $Y$.

Input Format

The input consists of two lines. Each line is a string of uppercase letters of length at most 200, representing the sequences $X$ and $Y$.

Output Format

The first line outputs a non-negative integer: the length of the longest common subsequence found.

Sample Input 1

ABCBDAB
BDCABA

Sample Output 1

4

Constraints

1s, 1024KiB for each test case.