Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#000249

Common Sequence

A subsequence of a given sequence is the given sequence with some elements (possible none) left out.

Given a sequence X = <x1, x2, ..., xm> and 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, xi{{j}} = zj.

For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>.

Given two sequences X and Y the problem is to find the
length of the maximum-length common subsequence of X and Y.



InputThe first line contains the string X. The second line contains the string Y. Both strings contain at least one, and not more than 1000 elements.


OutputPrint the length of the maximum-length common subsequence of X and Y.


Input:aleks
abcdef
Output:2


Input:abc
def
Output:0

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.