P4303 [AHOI2006] Gene Matching

Kaka dreamed last night that he and Keke arrived on another planet. On this planet, organisms have DNA sequences formed by countless types of bases (on Earth there are only $4$ types). Even stranger, each type of base appears exactly $5$ times in any given DNA sequence. Thus, if a DNA sequence consists of $N$ distinct types of bases, its length must be $5N$. After waking up, Kaka told Keke about this strange dream. Keke has been studying the gene matching problem in bioinformatics, so he decided to write a simple DNA matching program for organisms on this strange planet. To describe the principle of gene matching, we first define the concept of a subsequence: if we arbitrarily pick some bases (characters) from a DNA sequence (string) $s$ and arrange them in the same order as in $s$ to form a new string $u$, then $u$ is called a subsequence of $s$. For two DNA sequences $s_1$ and $s_2$, if there exists a sequence $u$ that is a subsequence of both $s_1$ and $s_2$, then $u$ is called a common subsequence of $s_1$ and $s_2$. Given two DNA sequences $s_1$ and $s_2$, the maximum match is defined as the length of the longest common subsequence of $s_1$ and $s_2$. [Task] Write a program to: - Read two DNA sequences of equal length from the input file. - Compute their maximum match. - Print your result to the output file.

The first line contains an integer $N$, meaning that a certain organism on this planet uses $N$ distinct types of bases, numbered by the integers $1 \ldots N$. The next two lines each describe a DNA sequence: each contains $5N$ integers in the range $1 \ldots N$, and every integer appears exactly $5$ times in the corresponding sequence.

Output a single integer: the maximum match of the two DNA sequences.

$1 \leq N \leq 20000$. Translated by ChatGPT 5