| 题目名称 | 1134. DNA螺旋串 |
|---|---|
| 输入输出 | lcsdna.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 5 |
| 题目来源 |
 cqw
于2012-10-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：67， 提交：140， 通过率：47.86% | ||||
 皮波Forever |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_ |
100 | 0.000 s | 0.00 MiB | C++ |
|
皮波Forever |
100 | 0.000 s | 0.00 MiB | C++ |
 AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
|
AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
|
AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
 派特三石 |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_chairman |
100 | 0.000 s | 0.00 MiB | C++ |
 金身人面兽 |
100 | 0.000 s | 0.00 MiB | C++ |
 LOSER |
100 | 0.000 s | 0.00 MiB | C++ |
| 关于 DNA螺旋串 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
内存爆了……
| ||||
|
亲测2010的长度最大值可以过
| ||||
|
| ||||
|
| ||||
|
荣登榜首
 | ||||
|
GOOD BOY
| ||||
|
这题的数据略弱。。某些并未考虑字典序的程序都能过
| ||||
|
| ||||
竹语淡墨
Sky_miner
Go灬Fire
NewBee
SOBER GOOD BOY
liu_runda
【离开·再见】星裔·自由蒂兰【问题描述】
在生物学应用中，经常要比较两个(或更多)不同有机体的DNA。一个DNA螺旋由一串被称为基的分子组成，可能的基包括腺嘌呤(adenine)、鸟嘌呤(guanine)、胞嘧啶(cytosine)和胸腺嘧啶(thymine)。分别以它们的首字母来代表这些基，一个DNA螺旋可以表示为在有穷集合{A，C，G，T}上的一个串。例如，一个有机体的DNA可能为s1= ACCGGTCGAGTGCGCGGAAGCCGGCCGAA，而另一个有机体的DNA可能为S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA.
将两个DNA螺旋作比较的一个目的就是要确定这两个螺旋有多么"相似"，也就是关于这两个有机体的某些度量有多么接近。相似度可以而且已经用很多不同方式来定义。例如，我们可以说两个DNA螺旋相似，如果其中一个是另一个的子串。在我们的例子中，S1或S2都不是另一方的子串。或者，我们可以说两个螺旋相似，如果把其中一个转换成另一个所需改变的数量很小。另外一个度量螺旋S1和S2相似度的方式是找出第三个螺旋S3，在S3中的基也都出现在S1和S2中；而且这些基必须是以相同的顺序出现，但是不必要是连续的。能找到的S3越长，S1和S2就越相似。在我们的例子中，最长的螺旋S3是GTCGTCGGAAGCCGGCCGAA
【输入格式】
第一行：基因串1
第二行： 基因串2
【输出格式】
第一行：最长的基因串的长度
第二行：最长基因串
如果有多个，输出字典序最小的。
【输入样例】
ACCGGTCGAGTGCGCGGAAGCCGGCCGAA GTCGTTCGGAATGCCGTTGCTCTGTAAA
【输出样例】
20 GTCGTCGGAAGCCGGCCGAA