Jun*_*jie 5 string algorithm
给定一个字符串的子序列集合.
例如:
abc acd bcd
问题是,如何从这些序列中确定最短的字符串？
对于上面的例子,最短的字符串是abcd.
abcd
这里子序列表示字符串的一部分但不一定是连续的.喜欢acd是字符串的子序列abcd.
acd
编辑:这个问题实际上来自Project Euler问题79,在那个问题中,我们有50个子序列,每个子序列的长度为3.所有字符都是数字.
Pen*_*ang 5
这个问题得到了很好的研究,并创造了" 最短的常见超级序列 "
对于两个字符串,它在O(n)中.假设n是字符串的最大长度.O(n)用于构建后缀数组,然后用O(n)来解决最长公共子序列问题.
对于两个以上的字符串,它是NP-Complete.
归档时间：
12 年，1 月 前
查看次数：
1290 次
最近记录：
11 年，9 月 前