DNA Similarity

Every DNA sequence is written with the four letters A, C, G, and T.

The similarity of two DNA sequences is computed after inserting blanks at arbitrary positions so the two sequences have the same length.

• Add 3 points when the same position contains the same non-blank letter.
• Subtract 2 points when the two letters are different, or when one of the two positions is blank.

The similarity of the two sequences is the maximum score obtainable over all possible ways to insert blanks. For example, AGTCAG and ATGTG can be aligned as follows.

A G T C A G|   |     |A   T G T G

This alignment has score 3. Another alignment is shown below.

A   G T C A G|   | |     |A T G T     G

This alignment has score 6. Therefore, the similarity of the full sequences AGTCAG and ATGTG is 6.

A substring of a DNA sequence is a sequence obtained by taking one contiguous interval of the original sequence. For example, taking the first through third letters of AGTCAG gives AGT, and taking the second through fifth letters gives GTCA.

To find parts of two DNA sequences that are likely to contain the same information, choose one substring from each sequence and maximize the similarity between the chosen substrings. For example, choosing AGT from AGTCAG and ATGT from ATGTG gives score 7 with the alignment below.

A   G T|   | |A T G T

Given two DNA sequences, output the maximum similarity among all pairs of substrings and one pair of substrings that attains it.

The first line contains the length of the first DNA sequence. The second line contains the first DNA sequence. The third line contains the length of the second DNA sequence. The fourth line contains the second DNA sequence.

Each DNA sequence has length at most 1000, and there are no spaces between the characters of a sequence. The two DNA sequences have at least one character in common.

On the first line, output the maximum similarity among all pairs of substrings of the two DNA sequences.

On the second line, output the substring chosen from the first DNA sequence. On the third line, output the substring chosen from the second DNA sequence. If more than one pair of substrings has the maximum similarity, output any one of them.