1

如果我想找到 2 个字符串的最长公共子字符串，那么哪种方法在时间/空间复杂度方面更有效：使用 DP 的后缀数组？

DP 将产生 O(m*n) 空间，时间复杂度为 O(m*n)，后缀数组方法的时间复杂度是多少？

1) 计算后缀 O(m) + O(n) 2) 排序 O(m+n log2(m+n)) 3) 找到 m+n-1 个字符串的最长公共前缀？[我不确定如何计算 #of 比较]

后缀数组允许我们对子字符串做更多的事情（比如搜索子字符串等），但是由于在这种情况下不需要其他函数，DP 是否会被认为是一种更简单/更清洁的方法？哪一个应该在我们比较 2 个字符串的情况下使用？

另外，如果我们有超过 2 个字符串怎么办？

4

1 回答 1

0

后缀数组会更好。LCS（n个字符串的最长公共子串）问题可以解决如下：

  1. 连接 S1, S2, ..., Sn 如下： S = S1$1S2$2...$nSn，这里 $i 是特殊符号（哨兵），它们与初始字母表的其他符号不同且在字典上少于其他符号。
  2. 计算后缀数组。通常，我们在 O(n*log n) 中实现后缀数组，但是有一个重要的算法称为 DC3，它计算后缀数组的时间为 O(n)，n 是 N 个字符串的总长度。你可以google这个算法。
  3. 计算所有相邻后缀的 LCP。
于 2013-06-17T14:56:42.573 回答