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
3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Sample Output
no significant commonalities
AGATAC
CATCATCAT
题意:给你m组DNA 要求你找到 最长公共的子串
思路:以第一个字符串为准 枚举 起点为 j 长度为 i 的子串 然后对其他字符串进行匹配(这个算法也是比较慢了)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long int
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[]={,,,,,,,,,,,,};
int dir[][]={, ,, ,-, ,,-};
int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};
const int inf=0x3f3f3f3f;
const ll mod=1e9+;
string s[];
int dp[];
void getnext(string t){
dp[]=;
for(int i=,j=;i<=t.length();i++){
while(j>&&t[i-]!=t[j]) j=dp[j];
if(t[i-]==t[j]) j++;
dp[i]=j;
}
}
bool kmp(string t,string p){
int len1=p.length();
int len2=t.length();
for(int i=,j=;i<=len1;i++){
while(j>&&p[i-]!=t[j]) j=dp[j];
if(p[i-]==t[j]) j++;
//cout<<j<<endl;
if(j==len2)
return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
while(n--){
int m;
cin>>m;
for(int i=;i<m;i++)
cin>>s[i];
int len=s[].length();
string ans="";
for(int i=;i<=len;i++){
for(int j=;j<=len-i;j++){
string temp=s[].substr(j,i);
getnext(temp);
bool jug=;
for(int k=;k<m;k++)
jug&=kmp(temp,s[k]); //一假必假
if(jug){
if(ans.size()<temp.size()) ans=temp;
else if(ans.size()==temp.size()) ans=min(ans,temp);
}
}
//cout<<ans<<endl;
}
if(ans.size()<) cout<<"no significant commonalities"<<endl;
else cout<<ans<<endl;
}
return ;
}