Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2015. november 29.

November 29, 2015 10:40 AM – November 29, 2015 3:40 PM

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
University of Debrecen; Faculty of Informatics; v. 03/01/2019