如何在两个字符串中找到最长的子串？

Question

如何在两个字符串中找到最大公共子串？

- mindtree

---

你所说的子字符串是指连续的字符，还是按顺序抽取的一些字符？换句话说，“AL”是“APPLE”的子字符串吗？ - templatetypedef

ab是abc和akabr的常见子串。 - mindtree

Answer 1

可能会使用后缀树。为两个字符串创建树，然后使用这些结构查找共同的路径。

- OJ.

Answer 2

我认为你可以使用一种非常优雅的动态规划算法来解决这个问题，它的时间复杂度为O(mn)，空间复杂度也是O(mn)，其中m和n是每个字符串中字符的数量。这个想法基于以下递归公式。假设两个字符串为A = a₀ a₁ a₂ ... a_n-1和B = b₀ b₁ b₂ ... b_m-1，并查看它们的第一个字符a₀和b₀。那么有三种方法可以尝试找到最长的公共子序列：

1. 如果第一个字符相等，则一种选择是找到其余两个字符串的最长公共子序列，然后将第一个字符添加到匹配中。
2. 或者，您可以决定不匹配前两个字符。在这种情况下，一种选择是查看忽略第一个字符串的第一个字符时可以制作的最长公共子序列。
3. 最后，您还可以忽略第二个字符串的第一个字符。

这给了我们一个非常好的递归公式：

LCS(A[0 .. n], B[0 .. m]) = longest of {
  A[0] + LCS(A[1 .. n], B[1 .. m])   (if A[0] == B[0]),
         LCS(A[1 .. n], B[0 .. m]),
         LCS(A[0 .. n], B[1 .. m])
    }

作为我们的基本情况，任何字符串与空字符串的最长公共子串都是空字符串：

LCS (A[n .. n], B[i, m]) = ""
LCS (A[i .. n], B[m, m]) = ""

这里的“最长公共子串”的定义允许你计算出 LCS(A[i..n], B[j..m]) 的值，只要给定三个值：LCS(A[i+1..n], B[j+1..m])、LCS(A[i..n], B[j+1..m]) 和 LCS(A[i+1..n], B[j..m])。因此，如果按正确顺序计算这些值，你可以在一次遍历中将结果填入表格并构造出结果。利用一些标准 DP 技巧，可以将其运行时间降至 O(mn)。

- templatetypedef

Answer 3

基本上有两种方式：1. 动态规划，时间和空间复杂度均为O(mn)。“templatetypedef”已经回答了这个问题。2. 后缀树，需要先构建它，带后缀链接的构建过程是O(m+n)（时间和空间），不带后缀链接则是O((m+n)^2)（时间）。虽然在最好情况下后缀树构建过程与动态规划具有相同效率，但是，在构建后缀树之后，您可以在O(k)时间内获得最长公共子串（k是LCS的长度）。

- Raphael