Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10083 | Accepted: 4262 |
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个序列*有的最长的子串,长度小于3的输出no significant commonalities,长度相等时输出字典序小的;
解题思路:枚举第一个序列的所有子串,每枚举出一个检查该子串是否是m个序列共有的,若是,比较该串与ans[]的长度取较长的,若长度相等取字典序小的;当枚举完所有子串后,ans[]保存的就是m个序列共有的最长的串。
#include<stdio.h>
#include<string.h> int main()
{
int i,j,k,n,t;
char DNA[][],tmp[],ans[];
scanf("%d",&t);
while(t--)
{
ans[] = '\0';
scanf("%d",&n);
for(i = ; i < n; i++)
scanf("%s",DNA[i]);
for(i = ; i < ; i++)//枚举子串的起点
{
for(j = i+; j < ; j++)//枚举子串的终点
{
int cnt = ;
for(k = i; k <= j; k++)
{
tmp[cnt++] = DNA[][k];
}
tmp[cnt] = '\0';//得到一个子串
for(k = ; k < n; k++)
{
if(strstr(DNA[k],tmp) == NULL)
break;
}
if(k < n) continue;
if(strlen(ans) == strlen(tmp))
{
if(strcmp(ans,tmp) > )
strcpy(ans,tmp);
}
else
{
if(strlen(tmp) > strlen(ans))
strcpy(ans,tmp);
}
}
}
if(strlen(ans) < ) printf("no significant commonalities\n");
else printf("%s\n",ans);
}
return ;
}
Blue Jeans(串)的更多相关文章
-
POJ 3080 Blue Jeans(串)
题目网址:http://poj.org/problem?id=3080 思路: 以第一个DNA序列s为参考序列,开始做以下的操作. 1.将一个字母s[i]作为匹配串.(i为当前遍历到的下标) 2.遍历 ...
-
POJ 3080 Blue Jeans(Java暴力)
Blue Jeans [题目链接]Blue Jeans [题目类型]Java暴力 &题意: 就是求k个长度为60的字符串的最长连续公共子串,2<=k<=10 规定: 1. 最长公共 ...
-
poj3080 Blue Jeans【KMP】【暴力】
Blue Jeans Time Limit: 1000MS Memory Limit: 65536K Total Submissions:21746 Accepted: 9653 Descri ...
-
(字符串 KMP)Blue Jeans -- POJ -- 3080:
链接: http://poj.org/problem?id=3080 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88230#probl ...
-
POJ 3080 Blue Jeans 找最长公共子串(暴力模拟+KMP匹配)
Blue Jeans Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20966 Accepted: 9279 Descr ...
-
POJ Blue Jeans [枚举+KMP]
传送门 F - Blue Jeans Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u ...
-
POJ 3080 Blue Jeans (求最长公共字符串)
POJ 3080 Blue Jeans (求最长公共字符串) Description The Genographic Project is a research partnership between ...
-
poj 3080 Blue Jeans
点击打开链接 Blue Jeans Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10243 Accepted: 434 ...
-
POJ3080——Blue Jeans(暴力+字符串匹配)
Blue Jeans DescriptionThe Genographic Project is a research partnership between IBM and The National ...
随机推荐
-
无题 MVC
1. MVC 里controller 返回匿名类型, 在View里是访问不了匿名类型的字段,因为它是Internal Private, 必须定义强类型 2. 扩展view的方法 public stat ...
-
dell inspiorn 14vr 1616b ubuntu 无线网卡的问题
找到两个解决方法: 1 找 网卡驱动下载: 用命令 以下 from :http://zhidao.baidu.com/link?url=k6QNIdJlbRyZJSEW1cVUs_1p4Jv-73c8 ...
-
CoreAnimation实现一个折线表
将折现表封装到一个view里,暴露给使用者的只有一个传入数据的方法. // // ChartLine.h // BoxingChampion //功能:根据传入的数组,绘制折线图 注意 其frame的 ...
-
今天遇到了隐藏顶部菜单栏(top bar)的菜鸟问题,解决了。
self.navigationController.navigationBarHidden = YES; http://*.com/questions/3397381/hide ...
-
python 简史
---恢复内容开始--- Python的作者,Guido von Rossum,确实是荷兰人.1982年,Guido从阿姆斯特丹大学(University of Amsterdam)获得了数学和计算机 ...
-
编译libcurl支持https协议
编译与安装参考:http://www.cnblogs.com/openiris/p/3812443.html 注意事项:先下载安装完nasm和perl再打开控制台(需要将nasm安装路径添加到Path ...
-
安装setuptools 报错缺少zlib
# yum install zlib # yum install zlib-devel 下载成功后,进入python2.7的目录,重新执行 #make #make install 此时先前执行的 软连 ...
-
自定义滤镜 ColorMatrixFilter
var url:URLRequest = new URLRequest("Koala.jpg"); var l:Loader = new Loader(); l.contentLo ...
-
ADO.Net练习1
一. 1.Car表数据查出显示2.请输入要查的汽车名称: 请输入要查的汽车油耗: 请输入要查的汽车马力: static void Main(string[] args) { SqlCo ...
-
2018.09.19 atcoder Card Game for Three(组合数学)
传送门 简单组合数学想优化想了半天啊233. 我们只需考虑翻开n张A,b张B,c张C且最后一张为A的选法数. 显然还剩下m+k−b−cm+k-b-cm+k−b−c张牌没有选. 这样的话无论前n+b+c ...