一开始我以为是字典树的啊、、后来发现没有思路啊、、看了discuss后知道了可以暴力过掉、、可是自己敲的时候竟然连样例都没有过掉啊、、后来发现思路是不对的啊、、看了discuss里的代码，感觉写的真不错啊、、、就学习了啊，就很轻松的过掉了啊、、由于我是菜鸟这是我第一次使用strstr函数、、也在这里纪念一下啊、、呵呵、、
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 10157 | Accepted: 4305 |
Description
As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers.
A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC.
Given a set of DNA base sequences, determine the longest series of bases that occurs in all of the sequences.
Input
- A single positive integer m (2 <= m <= 10) indicating the number of base sequences in this dataset.
- m lines each containing a single base sequence consisting of 60 bases.
Output
of the same longest length exist, output only the subsequence that comes first in alphabetical order.
Sample Input
3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Sample Output
no significant commonalities AGATAC CATCATCAT
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int main()
{
char str[20][100], st[100], s[100];
int i, j, n, m, k, h, num, ans, len;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
getchar();
for(i = 0; i < m; i++)
gets(str[i]);
len = strlen(str[0]);
ans = 0;
for(i = 0; i < len; i++)
{
for(j = i; j < len; j++)
{
num = 0;
for(k = i; k <= j; k++)
st[num++] = str[0][k];
st[num] = 0;
for(h = 1; h < m; h++)
if(strstr(str[h] , st) == 0)
break;
if(h == m && ans < num)
{
ans = num;
strcpy(s,st);
}
else if(h == m && ans == num)
{
if(strcmp(s,st) > 0)
strcpy(s,st);
}
}
}
if(ans < 3)
printf("no significant commonalities\n");
else puts(s);
}
return 0;
}