f*******y
发帖数: 988 | 1 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
比如
123
234
答案就是1234
12
21
11
12
答案就是
1121 |
a*****u
发帖数: 1712 | 2 难
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
|
f*******y
发帖数: 988 | 3 怎么做，完全不会
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
j****g
发帖数: 591 | 4
这个答案难道不是 1121 ?
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
|
f*******y
发帖数: 988 | 5 啊，对，看来人脑做是不太靠谱
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
|
s*******s
发帖数: 1031 | 6 N个字符串是相同长度？
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
|
l***i
发帖数: 1309 | 7 you want hamitonian path, not eulerian path, shortest superstring is NP-hard |
a********m
发帖数: 15480 | |
b***e
发帖数: 1419 | 9 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
|
a********m
发帖数: 15480 | 10 旅行商是np hard
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
|
