Finding similarities in character strings is an important problem in text processing and data mining. It has applications in genetics research as well, since strands of DNA can be expressed as very long strings of the characters C, G, T, and A.
A string s is said to be a subsequence of string t if the characters of s appear in order within t, but possibly with gaps between occurrences of each character. For example, ``COAT'' is a subsequence of ``ACROBATS'' since these characters occur in the same order within this string ``ARBS''. ``COBRA'' is not a subsequence of ``ACROBATS'', because even though all the characters appear, they do not appear in the proper order, and ``COBBS'' is not a subsequence because a character cannot be used twice.
To make this formal, break s and t into their individual characters
as: 
and let 
. We define
s to be a subsequence of t if there exists a sequence of
integers 
such that for
, we have 
.
One common way to measure the similarity of two character strings is to determine the length of their longest matching subsequence. For example, the sequences ``ABRACADABRA'' and ``YABBADABBADOO'' share the subsequence ``ABADABA'', whose length is 7.
RCAR YBBDOO
For this problem you will input two character strings and output their longest matching subsequence and its length. In some cases there may be more than one longest subsequence, in which case you may output any of them. (For example, given the strings ``ABCD'' and ``ACBD'' your program could output either ``ABD'' or ``ACD''.)
The input consists of two lines, each containing a string. Each string will contain from 0 to at most 15 characters.
The output consists of four lines. On the first and second lines, output the two input strings after the headers ``First string: '' and ``Second string: '', respectively. On the third line output ``Similarity: '' and the length of the longest matching subsequence. On the second line output ``LMS: '' and the longest matching subsequence.
Input:
ABRACADABRA YABBADABBADOO
Output:
First string: ABRACADABRA Second string: YABBADABBADOO Similarity: 7 LMS: ABADABA
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |