POJ 3080 Blue Jeans (求最长公共字符串）
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
Sample Input
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Sample Output
no significant commonalities
AGATAC
CATCATCAT
题意：给定长度为60的m个字符串，找它的最长公共子串，如果长度相同，输出字典序小的，如果找到的公共子串小于3 ，就输出 一串不认识的字母，否则就输出找到的那一串同样不认识的字母。
注意到，这个题给的数据范围很小，m不大于10，长度不大于60，吐过暴力枚举的话，复杂度大概是60*60*10*（60+60），不会爆，所以果断枚举，
暴力找就行，枚举相同序列的长度以第一个DNA为模板向其他串中找。其中有个技巧性的地方就是strstr（）函数的使用，strstr(a,b)函数为在a中找b，如果可以找到b那么会返回最初始找到b时的位置的地址，若找不到b则返回NULL。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm> using namespace std; int main()
{
//freopen("sample.txt","r",stdin);
int n;
scanf("%d",&n);
while(n--)
{
char str[][];
char ans[];
ans[]=;
int m;
scanf("%d",&m);
getchar();
for(int i=;i<m;i++)
{
gets(str[i]);
}
for(int i=;i<=strlen(str[]);i++)
{
int af=;
for(int j=;j<=strlen(str[])-i;j++)
{
int flag=;
char ttm[];
strncpy(ttm,str[]+j,i);
ttm[i]=;
for(int g=;g<m;g++)
{
if(!strstr(str[g],ttm))
{
flag=;
break;
}
}
if(flag)
{
af=;
if(strlen(ttm)>strlen(ans))
strcpy(ans,ttm);
else if(strlen(ttm)==strlen(ans)&&strcmp(ttm,ans)<)
strcpy(ans,ttm);
}
}
if(!af)
break;
}
if(strlen(ans)<)
printf("no significant commonalities\n");
else
puts(ans);
}
return ;
}