hdu 3080 (KMP + 매 거 진)
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 10119
Accepted: 4280
Description
The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated.
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
Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each dataset consists of the following components:
Output
For each dataset in the input, output the longest base subsequence common to all of the given base sequences. If the longest common subsequence is less than three bases in length, display the string "no significant commonalities" instead. If multiple subsequences 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
Source
South Central USA 2006
HDU 2328
이 문 제 는 여러 문자열 의 가장 긴 공통 문자열 을 요구 합 니 다.
가장 긴 공통 문자열 을 구 하 는 것 은 흔히 볼 수 있 는 알고리즘 이다.그러나 이 문 제 는 흔 한 두 문자열 의 DP 방법 을 제외 한 여러 문자열 을 원 합 니 다.
접미사 배열 을 사용 할 수 있 지만, 나 는 방금 접미사 배열 을 접 했 기 때문에 유연 하 게 사용 할 수 없다.
KMP + 매 거 를 시도 해 보 았 지만 시간 을 초과 하지 않 았 습 니 다.
가장 짧 은 문자열 을 찾 아 이 문자열 의 하위 문자열 을 매 거 진 다음 각각 다른 문자열 과 KMP 를 만 들 고 길이 가 가장 길 고 길이 가 같은 경우 사전 순서 가 가장 작은 공공 하위 문자열 을 찾 습 니 다.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=60+10;
char str[10+10][MAXN];
int next[MAXN];
//KMP next[]
void getNext(char *p)
{
int j,k,len=strlen(p);
j=0;
k=-1;
next[0]=-1;
while(j<len)
{
if(k==-1||p[j]==p[k])
{
next[++j]=++k;
}
else k=next[k];
}
}
// T S
// 0 , -1。
int KMP_Index(char *W,char *T)
{
int i=0, j=0,wlen=strlen(W),tlen=strlen(T);
getNext(W);
while(i<tlen&&j<wlen)
{
if(j==-1||T[i]==W[j])
{
i++; j++;
}
else
j=next[j];
}
if(j==wlen)
return i-wlen;
else
return -1;
}
int main()
{
int cas,n,i,j,k,Minlen,Minid;
char tmp[MAXN],ans[MAXN];
bool flag;
cin>>cas;
while(cas--)
{
scanf("%d",&n);
scanf("%s",str[0]);
Minlen=strlen(str[0]);
flag=false;
for(i=1;i<n;i++)
{
scanf("%s",str[i]);
Minid=0;
if(strlen(str[i])<Minlen)
{
Minid=i;Minlen=strlen(str[i]);
}
}
// printf("str[Minid]=%s
",str[Minid]);
ans[0]=0;
for(i=Minlen;i>=0;i--)
{
for(j=0;j<=Minlen-i;j++)
{
strncpy(tmp,str[Minid]+j,i);
tmp[i]=0;
// printf("tmp=%s
",tmp);
for(k=0;k<n;k++)
{
if(k!=Minid)
{
if(KMP_Index(tmp,str[k])==-1)
break;
}
}
if(k==n)
{
if(strlen(ans)<i)
strcpy(ans,tmp);
else if(strlen(ans)==i&&strcmp(ans,tmp)>0)
strcpy(ans,tmp);
flag=true;
}
}
//if(flag)break;
}
if(strlen(ans)<3)
printf("no significant commonalities
");
else printf("%s
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.