Description
A subsequence of one given sequence is the given sequence with some (or none)
elements left out, and the relative order of the elements are kept unchanged.
Given a sequence X = ⟨x1; x2; :::; xm⟩, another sequence Z = ⟨z1; z2; :::; zk⟩ is a
subsequence of X if there exists a strictly increasing sequence ⟨i1, i2, ..., ik⟩ of
indices of X such that for all j = 1; 2; :::; k: xij = zj .
For example, Z = ⟨a; b; f; c⟩ is a subsequence of Z = ⟨a; b; c; f; b; c⟩ with index
sequence ⟨1; 2; 4; 6⟩. Given two sequences X and Y , the problem is to nd the
length of the maximum-length common subsequence of X and Y .
The program input is from a text le. Each data set in the le contains
two strings representing the given sequences. The sequences are separated by
any number of white spaces. The input data are correct. For each set of data
the program prints on the standard output the length of the maximum-length
common subsequence from the beginning of a separate line.
Input
There exists multiple cases. Each case has only one line includes two strings
of characters which ranged from `a' to `z' representing the given sequences sep-
arated by a white spaces. Both of strings' length are no more than 1000.
Output
For each case you should output the length of the maximum-length common
subsequence in a line.