Problem D (ACM ICPC Philippines 2007)

ACM ICPC Philippines 2007
First Philippine National Inter-Collegiate Programming Competition
20 October 2007, De La Salle Canlubang
Organized by the Computing Society of the Philippines
in cooperation with Association for Computing Machinery


Problem D: Longest Common Subsequence
(Input File: pd.in)

Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:

abcxyz
dahcjyk

is acy of length 3.

The input of your program consist of pairs of lines where the first line is the first sequence of characters and the second line is the second sequence of characters. Each sequence is on a separate line and consists of at most 1,000 characters.

For each subsequent pair of input lines, output a line containing one integer number which satisfies the criteria stated above.

Sample input:

abcdefgh
azbxcydwe
1a2b3c4d
aa1bb2cc3dd
abcdefghijklmnopqrstuvwxyz
a1b2c3d4e5f6g7h8i9j0k1l2m3n4o5p6q7r8s9t0u1v2w3x4y5z6

Output for the sample input:

5
4
26