Description

A subsequence of a given sequence is obtained by deleting zero or more elements from the sequence.

More precisely, given a sequence X=<x~1~,x~2~,…,x~m~>, another sequence Z=<z~1~,z~2~,…,z~k~> is a subsequence of X if there exists a strictly increasing sequence of indices <i~1~,i~2~,…,i~k~> such that for all j=1,2,…,k:

$X_{ij}=Zj$

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, if another sequence Z is a subsequence of both X and Y, then Z is called 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 (LCS) of X and Y, because X and Y have no common subsequence longer than 4.

Given two sequences X=<x~1~,x~2~,…,x~m~> and Y=<y~1~,y~2~,…,y~n~>, the task is to find an LCS of X and Y.

Input Format

There are two lines. Each line contains a string composed of uppercase letters, with a length not exceeding 1000, representing sequences X and Y.

Output Format

The first line contains a non-negative integer, representing the length of the longest common subsequence. If no common subsequence exists, the output file should contain only one line with the integer 0.

ABCBDAB
BDCABA

4

Hint

The difference between the longest common substring (Longest Common Substring) and the longest common subsequence (Longest Common Subsequence, LCS) is as follows: A substring is a contiguous part of a string, whereas a subsequence is derived by deleting zero or more elements from the sequence without changing the order of the remaining elements. In other words, the characters in a substring must occupy consecutive positions in the original string, while a subsequence does not require continuity. The length of the string is less than or equal to 1000.