a*u
2 楼
难
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
f*y
3 楼
怎么做，完全不会
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
【在 a*****u 的大作中提到】
: 难
:
: ★ 发自iPhone App: ChineseWeb 7.8
j*g
4 楼
这个答案难道不是 1121 ?
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
f*y
5 楼
啊，对，看来人脑做是不太靠谱
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
【在 j****g 的大作中提到】
:
: 这个答案难道不是 1121 ?
s*s
6 楼
N个字符串是相同长度？
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
产生一个有向图，每个节点代表一个数字，比如12
(n1, n2)是个有向边 iff n1去掉第一个字符是n2的前缀。
计算欧拉路径，就可以生成最小串了。
大牛看看我的想法靠谱不？
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
l*i
7 楼
you want hamitonian path, not eulerian path, shortest superstring is NP-hard
a*m
8 楼
难。。。。
b*e
9 楼
这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
误解。
【在 f*******y 的大作中提到】
: 给定N个字符串，生成一个最小长度的字符串X，使的N个字符串全是X的子串
: 比如
: 123
: 234
: 答案就是1234
: 12
: 21
: 11
: 12
: 答案就是
a*m
10 楼
旅行商是np hard
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
【在 b***e 的大作中提到】
: 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
: 误解。
相关阅读
问一个投简历的问题，是不是伤人品了？QA need (Zynga)请教关于 F的电面刚工作2个月可以申请其他工作么？TSC card production快3周了，想杀人了Finished my job seeking和recruiter谈的时候，需要亮出现在的年薪吗？？？面试题：GetNumber and ReleaseNumber求助，马上要答复，急! H1b申请问题～【急询】关于OPT的问题公司要用Skype 来跟我谈，请问要视频么？问一下H1-B批了以后自己应该拿到什么大家给介绍一下写RESUME的经验吧? (转载)在学校TA/RA工作的时间填每周多少小时？经济不好 找工作去加州还是去纽约？Recruiting Entry Level 2 years Quantitative Analytics Resea (转载)求教一个Java TTD 测试驱动的 面试题现在刚毕业的还能找到java方面的工作么？问一个问题，关于保险收到了mail的offer 还能negotiate offer吗