2/3字符串的最长公共子字符串：后缀数组与动态编程方法

Question

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

DP将产生具有O（m * n）时间复杂度的O（m * n）空间，那么后缀数组方法的时间复杂度是多少？

1）计算后缀O（M）+ O（n）的 2）对它们进行排序O（M + N的log 2（M + N）） 3）寻找对于m + n-1个字符串最长的共同前缀？ [我不知道如何计算#of比较]

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

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

Answer 1

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

1. 串联S1，S2，...，Sn为如下： S = S1 $ 1S2 $ 2 ... $ NSN，以下$ i是不同的特殊符号（哨兵），并且 按字母顺序小于初始字母表中的其他符号。
2. 计算后缀数组。一般来说，我们在O（n * log n）中实现了后缀数组，但是有一个重要算法叫做DC3，它计算O（n）中的后缀数组，n是N个字符串的总长度。你可以谷歌这个算法。
3. 计算所有相邻后缀的LCP。