PROGRAMMING:Base sequence matching
The geography project is a collaborative research project between IBM and the National Geographic Society to analyze how humans on earth reproduce from thousands of donated DNA.
As an IBM researcher, please write a program to find out the similarities between the given DNA fragments, so that the individual investigation can be correlated.
A DNA base sequence refers to the sequence of nitrogen groups found in molecules. There are four nitrogen groups: adenine (a), thymine (T), guanine (g), and cytosine (d). For example, a 6-base DNA sequence can be expressed as tagacc.
Given a set of DNA base sequences, determine the longest base sequence in all sequences.
###Input format:
The first line of input gives the integer n, which represents the number of test data sets. Each test data set consists of the following two parts:
A positive integer m (2 ≤ m ≤ 10) gives the number of base sequences in the data set.
Each row gives a 60 base sequence.
###Output format:
For all base sequences of each test data set input, the longest identical base subsequence is output.
If the length of the longest identical base sub sequence is less than 3, "no significant commonalities" is output instead of the base sub sequence.
If there are multiple subsequences of the same longest length, only the first one in alphabetical order is output.
###Input example:
```in
three
two
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
three
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
three
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
```
###Output example:
```out
no significant commonalities
AGATAC
CATCATCAT
```
###Label:
String, BF algorithm, KMP algorithm
###Source:
ACM South Central USA 2006
answer：If there is no answer, please comment
As an IBM researcher, please write a program to find out the similarities between the given DNA fragments, so that the individual investigation can be correlated.
A DNA base sequence refers to the sequence of nitrogen groups found in molecules. There are four nitrogen groups: adenine (a), thymine (T), guanine (g), and cytosine (d). For example, a 6-base DNA sequence can be expressed as tagacc.
Given a set of DNA base sequences, determine the longest base sequence in all sequences.
###Input format:
The first line of input gives the integer n, which represents the number of test data sets. Each test data set consists of the following two parts:
A positive integer m (2 ≤ m ≤ 10) gives the number of base sequences in the data set.
Each row gives a 60 base sequence.
###Output format:
For all base sequences of each test data set input, the longest identical base subsequence is output.
If the length of the longest identical base sub sequence is less than 3, "no significant commonalities" is output instead of the base sub sequence.
If there are multiple subsequences of the same longest length, only the first one in alphabetical order is output.
###Input example:
```in
three
two
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
three
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
three
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
```
###Output example:
```out
no significant commonalities
AGATAC
CATCATCAT
```
###Label:
String, BF algorithm, KMP algorithm
###Source:
ACM South Central USA 2006
answer：If there is no answer, please comment