Blue Jeans(串)

时间:2021-07-11 15:23:58
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 10083   Accepted: 4262

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:
  • 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

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 题意:寻找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(串)的更多相关文章

  1. POJ 3080 Blue Jeans&lpar;串&rpar;

    题目网址:http://poj.org/problem?id=3080 思路: 以第一个DNA序列s为参考序列,开始做以下的操作. 1.将一个字母s[i]作为匹配串.(i为当前遍历到的下标) 2.遍历 ...

  2. POJ 3080 Blue Jeans&lpar;Java暴力&rpar;

    Blue Jeans [题目链接]Blue Jeans [题目类型]Java暴力 &题意: 就是求k个长度为60的字符串的最长连续公共子串,2<=k<=10 规定: 1. 最长公共 ...

  3. poj3080 Blue Jeans【KMP】【暴力】

    Blue Jeans Time Limit: 1000MS   Memory Limit: 65536K Total Submissions:21746   Accepted: 9653 Descri ...

  4. (字符串 KMP)Blue Jeans -- POJ -- 3080&colon;

    链接: http://poj.org/problem?id=3080 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88230#probl ...

  5. POJ 3080 Blue Jeans 找最长公共子串(暴力模拟&plus;KMP匹配)

    Blue Jeans Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 20966   Accepted: 9279 Descr ...

  6. POJ Blue Jeans &lbrack;枚举&plus;KMP&rsqb;

    传送门 F - Blue Jeans Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u ...

  7. POJ 3080 Blue Jeans &lpar;求最长公共字符串)

    POJ 3080 Blue Jeans (求最长公共字符串) Description The Genographic Project is a research partnership between ...

  8. poj 3080 Blue Jeans

    点击打开链接 Blue Jeans Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10243   Accepted: 434 ...

  9. POJ3080——Blue Jeans&lpar;暴力&plus;字符串匹配&rpar;

    Blue Jeans DescriptionThe Genographic Project is a research partnership between IBM and The National ...

随机推荐

  1. 无题 MVC

    1. MVC 里controller 返回匿名类型, 在View里是访问不了匿名类型的字段,因为它是Internal Private, 必须定义强类型 2. 扩展view的方法 public stat ...

  2. dell inspiorn 14vr 1616b ubuntu 无线网卡的问题

    找到两个解决方法: 1 找 网卡驱动下载: 用命令 以下 from :http://zhidao.baidu.com/link?url=k6QNIdJlbRyZJSEW1cVUs_1p4Jv-73c8 ...

  3. CoreAnimation实现一个折线表

    将折现表封装到一个view里,暴露给使用者的只有一个传入数据的方法. // // ChartLine.h // BoxingChampion //功能:根据传入的数组,绘制折线图 注意 其frame的 ...

  4. 今天遇到了隐藏顶部菜单栏&lpar;top bar&rpar;的菜鸟问题,解决了。

    self.navigationController.navigationBarHidden = YES; http://*.com/questions/3397381/hide ...

  5. python 简史

    ---恢复内容开始--- Python的作者,Guido von Rossum,确实是荷兰人.1982年,Guido从阿姆斯特丹大学(University of Amsterdam)获得了数学和计算机 ...

  6. 编译libcurl支持https协议

    编译与安装参考:http://www.cnblogs.com/openiris/p/3812443.html 注意事项:先下载安装完nasm和perl再打开控制台(需要将nasm安装路径添加到Path ...

  7. 安装setuptools 报错缺少zlib

    # yum install zlib # yum install zlib-devel 下载成功后,进入python2.7的目录,重新执行 #make #make install 此时先前执行的 软连 ...

  8. 自定义滤镜 ColorMatrixFilter

    var url:URLRequest = new URLRequest("Koala.jpg"); var l:Loader = new Loader(); l.contentLo ...

  9. ADO&period;Net练习1

    一. 1.Car表数据查出显示2.请输入要查的汽车名称:     请输入要查的汽车油耗:     请输入要查的汽车马力: static void Main(string[] args) { SqlCo ...

  10. 2018&period;09&period;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 ...