| 题目名称 | 2128. [POJ3294]生命形态 |
|---|---|
| 输入输出 | Lifeforms.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mikumikumi
于2016-01-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：28， 提交：80， 通过率：35% | ||||
 Go灬Fire |
100 | 0.732 s | 3.86 MiB | C++ |
 MistyEye |
100 | 0.783 s | 3.47 MiB | C++ |
 chad |
100 | 0.926 s | 54.72 MiB | C++ |
|
MistyEye |
100 | 0.946 s | 31.79 MiB | C++ |
 _Horizon |
100 | 0.985 s | 23.21 MiB | C++ |
 FoolMike |
100 | 1.059 s | 11.24 MiB | C++ |
 stdafx.h |
100 | 1.082 s | 27.00 MiB | C++ |
 zys |
100 | 1.139 s | 27.86 MiB | C++ |
 confoo |
100 | 1.149 s | 4.33 MiB | C++ |
 Rapiz |
100 | 1.149 s | 4.33 MiB | C++ |
| 关于 生命形态 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Rapiz :
既没有字典序也没有去重，居然还有分…… | ||||
|
感觉细节很多（也可能是我代码写的太渣了
试一下n=1应该能出来很多错误 | ||||
【题目描述】
大多数的外星人的生命形态与人类相似，区别仅在表面上特征如肤色、身高、耳朵。一小部分没有人类的外表，他们的形状通常是几何物体或者无规则的物体，比如立方体，油状，或者粉尘状.
在《星际迷航》中指出生命形态由大量的公共DNA片段决定。
以字符串的形式给出几种生命形态的DNA序列，我们想知道在一半以上生命形态的DNA序列中出现的最长子串是什么。
【输入格式】
多组数据，第一行数一个n（1<=n<=100),代表生命形态的数量。之后的n行，每行一个字符串，代表DNA序列。如果n=0，则输入结束。
【输出格式】
对于每组输入，输出最长的，在一半以上生命形态的DNA序列中出现过的子串。如果有多个答案，按字典序将它们都输出。如果没有，则输出"?"。
每组输出间要有一行空行。
【样例输入】
3
abcdefg
bcdefgh
cdefghi
3
xxx
yyy
zzz
0
【样例输出】
bcdefg
cdefgh
?
【数据范围】
n<=100,每个字符串长度大于1且小于1000
【来源】
http://poj.org/problem?id=3294