Longest Common Subsequence in Alien DNAs

In a strange dream, Kaka saw himself and Coco on another planet where the DNA sequences of living beings are constructed with many types of bases (unlike Earth's four) and, curiously, each type of base appears exactly 5 times in any valid DNA sequence. Thus, if a DNA sequence comprises N distinct bases, its length must be 5N.

Inspired by this dream, Coco, who has been studying gene matching, decides to write a simple DNA matching program for the creatures on that planet. To explain the principle, we first define a subsequence. Given a DNA sequence (i.e. a string) s, if we can select some characters from s (not necessarily contiguous) while preserving their original order, the new string u is called a subsequence of s. For two DNA sequences s1 and s2, any sequence u that is a subsequence of both s1 and s2 is called a common subsequence.

Your task is to compute the Longest Common Subsequence (LCS) between two given DNA sequences. The length of the LCS is referred to as their maximum match.

The mathematical formulation for the LCS can be expressed using the recursive relation:

$$\text{dp}(i,j)=\begin{cases} 0, & \text{if } i=0 \text{ or } j=0,\\ \text{dp}(i-1,j-1)+1, & \text{if } s1[i]=s2[j],\\ \max(\text{dp}(i-1,j),\,\text{dp}(i, j-1)), & \text{otherwise.} \end{cases} $$

inputFormat

The input consists of two lines. Each line contains a DNA sequence. Both sequences are of equal length and are valid, i.e. if the sequence is composed of N different bases then its length equals 5N (each base appears exactly 5 times).

For example:

AAAAABBBBB
BBBBBAAAAA

outputFormat

Print a single integer representing the length of the longest common subsequence (LCS) of the two DNA sequences.

sample

AAAAABBBBB
AAAAABBBBB

10