Longest Common Subsequence

Sequence 1:

Sequence 2:

Given two sequences of characters, print the length of the longest common subsequence of both sequences.

For example, the longest common subsequence of the sequences “abcdgh” and “aedfhr” is “adh” of length 3.

Input Specification

The input consists of pairs of lines. The first line of a pair contains the first string, and the second line contains the second string. Each string is on a separate line and consists of at most 1000 characters.

Output Specification

For each subsequent pair of input lines, output a line containing one integer number satisfying the criterion stated above.

Sample Input

1. bcacbcabbaccbab
2. bccabccbbabacbc
3. a1b2c3d4e
4. zz1yy2xx3ww4vv
5. abcdgh
6. aedfhr
7. abcdefghijklmnopqrstuvwxyz
8. a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
9. abcdefghijklmnzyxwvutsrqpo
10. opqrstuvwxyzabcdefghijklmn

download as text file

Output for Sample Input

1. 11
2. 4
3. 3
4. 26
5. 14

download as text file