Hide

Problem B
DNA Similarity

/problems/baylor.dnasimilarity/file/statement/en/img-0001.jpg
Image by Andy Leppard.

Given two DNA sequences (strings of symbols a, c, g, t), calculate their similarity. For this problem we define similarity as the length of the longest subsequence that is common to both original sequences. A subsequence is a sequence of symbols that appears in a longer sequence in the same order, but with some symbols from the longer sequence possibly removed. For example, consider the following two sequences:

    agaatacg
    atagatcagg

The longest subsequence of both sequences is agatcg, with a length of $6$. Here are the original sequences again, but this time using uppercase letters to indicate the longest subsequence:

    AGaATaCG
    AtaGATCagG

Note that there may be more than one subsequence with the longest length.

Input

Input begins with an integer $n$ indicating the number of cases that follow, where $1 \le n \le 100$. Each test case has two lines which represent the two sequences to compare. Each sequence is non-empty and has up to $500$ characters, consisting only of the letters a, c, g, and t.

Output

For each pair of sequences, output the length of the longest common subsequence.

Sample Input 1 Sample Output 1
3
agaatacg
atagatcagg
accggat
accggat
gggaaaggg
aaaccc
6
7
3
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Greg Hamerly
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in