最长公共子串算法详解：原理与实现

发表于 2025/03/17

作者 smallbei 37 分钟阅读

一、基本概念

1. 什么是最长公共子串？

最长公共子串（Longest Common Substring）是指在两个或多个字符串中找出最长的共同连续子序列。这里的关键词是”连续”，这也是它与最长公共子序列的本质区别。

为了直观理解这个概念，考虑一个简单例子：字符串 “ABCDEF” 和 “BCDEGH” 的最长公共子串是 “BCDE”，长度为4。

最长公共子串具有三个核心特点：

连续性：子串中的字符必须在原字符串中连续出现，不能跳过任何字符
共同性：子串必须同时出现在所有目标字符串中，代表共同部分
最长性：在满足以上两个条件的所有子串中，长度最大的一个

2. 最长公共子串与最长公共子序列的区别

这两个概念在实际应用中经常被混淆，但它们有着明确的区别：

最长公共子串	最长公共子序列
要求连续	不要求连续
字符之间的相对位置和原字符串中相同	仅保持字符之间的相对顺序
通常使用动态规划或后缀数组解决	通常使用动态规划解决

以具体例子说明：对于字符串 “ABCDEF” 和 “ACBEF”：

最长公共子串是 “EF”，长度为2
最长公共子序列是 “ABEF”，长度为4

区分这两个概念至关重要，因为它们涉及不同的问题模型和解决方案。

3. 为什么需要研究最长公共子串？

最长公共子串算法在多个领域有着广泛而重要的应用，正是这些实际应用价值使它成为算法领域的经典问题：

生物信息学
- DNA序列比对：识别不同物种间的共同基因片段
- 基因组分析：发现基因组中的保守区域，帮助理解进化关系
- 蛋白质序列相似性分析：预测蛋白质功能和结构
自然语言处理
- 文本相似度计算：评估文档间的内容相似程度
- 抄袭检测：识别文本中可能抄袭的段落
- 关键词提取：从多个相关文档中提取共同重要信息
数据压缩
- 寻找重复数据段：减少冗余存储
- 实现增量备份：仅存储文件变化的部分
信息安全
- 模式匹配：检测已知攻击特征
- 入侵检测系统：识别可疑行为模式
软件开发
- 代码克隆检测：找出重复或相似的代码片段
- 版本控制中的差异比较：精确定位代码变更

理解最长公共子串算法不仅能帮助解决这些领域中的具体问题，还能加深对动态规划和字符串处理技术的理解。下面我们将详细介绍解决这类问题的多种算法方法。

二、最长公共子串的算法原理

掌握最长公共子串问题需要了解几种不同的解决方法，每种方法各有优缺点，适用于不同的场景。

1. 朴素方法

最直接的解决方法是枚举所有可能的子串并比较，这种直观方法虽然简单但效率较低：

具体步骤如下：

枚举第一个字符串的所有可能子串（对于长度为n的字符串，共有n*(n+1)/2个子串）
对于每个子串，检查它是否出现在第二个字符串中
记录并更新找到的最长公共子串

时间复杂度：O(n³)，其中n是字符串的长度，空间复杂度：O(1)

这种方法的实现直观易懂，但在处理较长字符串时性能表现不佳。例如，对于字符串 s1=”ABABC” 和 s2=”BABCA”：

依次检查s1的所有子串：{“A”, “AB”, “ABA”, “ABAB”, “ABABC”, “B”, “BA”, “BAB”, “BABC”, “C”}
对于每个子串，在s2中搜索
最终找到最长的公共子串：”BAB”，长度为3

2. 动态规划方法

动态规划是解决最长公共子串问题的经典方法，它通过构建和填充一个表格来有效跟踪子问题的解：

核心思想：

创建一个二维数组 dp[i][j]，表示以字符串A的第i个字符和字符串B的第j个字符结尾的最长公共子串长度
当两个字符相匹配时（A[i-1] == B[j-1]），我们可以基于之前的结果加1：dp[i][j] = dp[i-1][j-1] + 1
当字符不匹配时，由于子串要求连续，我们需要重置计数：dp[i][j] = 0

算法步骤：

创建一个 (m+1) × (n+1) 的二维数组，初始化为0
使用动态规划方程填充数组
记录表格中的最大值及其位置
根据最大值的位置回溯得到最长公共子串

动态规划方程可以表示为：

dp[i][j] = {
    dp[i-1][j-1] + 1,  如果 A[i-1] == B[j-1]
    0,                其他情况
}

这种方法的时间复杂度为O(mn)，空间复杂度为O(mn)，其中m和n是两个字符串的长度。

3. 后缀数组方法

对于处理长字符串或多字符串的情况，后缀数组是一种更高效的解决方案：

将两个字符串用一个特殊字符（如 ‘#’）连接起来形成新字符串
构建后缀数组和最长公共前缀（LCP）数组
扫描LCP数组找出最长公共子串

后缀数组方法特别适合处理多字符串的最长公共子串问题，其时间复杂度为O(n log n)，其中n是字符串的总长度。

后缀数组方法示例：

对于字符串 “banana” 和 “ananas”：

连接成 “banana#ananas”
生成所有后缀并排序
寻找排序后相邻后缀中，一个来自 “banana”，一个来自 “ananas” 的最长公共前缀
这个最长公共前缀就是原始字符串的最长公共子串，在本例中是 “ana”

4. 滑动窗口方法

滑动窗口是另一种解决最长公共子串问题的有效方法：

固定其中一个字符串的位置
滑动另一个字符串，使其逐个对齐
在每个对齐位置，计算最长公共子串的长度

时间复杂度：O(m*n)，其中m和n是两个字符串的长度

滑动窗口过程示意：

假设我们有字符串 s1=”ABCD” 和 s2=”BCDE”：

滑动位置1:       
A B C D
      B C D E
最长公共子串: 无

滑动位置2:       
A B C D
    B C D E
最长公共子串: 无

滑动位置3:       
A B C D
  B C D E
最长公共子串: "BCD", 长度为3

滑动位置4:       
A B C D
B C D E
最长公共子串: "BCD", 长度为3

滑动位置5:       
  A B C D
B C D E
最长公共子串: "CD", 长度为2

... 以此类推

通过系统地移动字符串并比较，可以找出最长的公共子串。

三、动态规划解法详解

1. 状态定义

在动态规划方法中，我们定义：

dp[i][j] = 以A的第i个字符和B的第j个字符结尾的最长公共子串的长度

这个定义非常重要，因为它告诉我们dp[i][j]只关心以A[i-1]和B[j-1]结尾的子串。状态定义是动态规划的核心，它决定了我们如何构建问题的解决方案。

2. 状态转移方程

dp[i][j] = {
    dp[i-1][j-1] + 1,  如果 A[i-1] == B[j-1]
    0,                其他情况
}

状态转移方程描述了子问题之间的关系：

当A的第i个字符和B的第j个字符相同时，当前位置的最长公共子串长度等于左上角位置的值加1
当字符不同时，由于子串必须连续，当前位置无法延续之前的匹配，因此重置为0

这种转移方程体现了最长公共子串的连续性要求，与最长公共子序列不同，这里当字符不匹配时我们直接重置计数。

3. 动态规划过程可视化

为了更好地理解动态规划解决最长公共子串问题的过程，下面通过一个具体示例进行说明：

假设我们有两个字符串：

s1 = “ABCDEF”
s2 = “BCDEGH”

步骤1: 初始化DP表格

首先，创建一个(m+1)×(n+1)的二维数组，其中m=6（s1的长度），n=6（s2的长度）。表格初始化为0：

    |  "" |  B  |  C  |  D  |  E  |  G  |  H  |
----|-----|-----|-----|-----|-----|-----|-----|
 "" |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 A  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 B  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 C  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 D  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 E  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 F  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |

步骤2: 填充DP表格

根据状态转移方程，逐行填充表格：

首先，对于第一行(i=1，对应s1[0]=’A’)，’A’与s2中的字符逐一比较：

‘A’与’B’不匹配，dp[1][1] = 0
‘A’与’C’不匹配，dp[1][2] = 0
…以此类推，第一行全部为0

第二行(i=2，对应s1[1]=’B’)：

‘B’与’B’匹配，dp[2][1] = dp[1][0] + 1 = 1
‘B’与’C’不匹配，dp[2][2] = 0
…以此类推

逐行填充后，最终表格如下：

    |  "" |  B  |  C  |  D  |  E  |  G  |  H  |
----|-----|-----|-----|-----|-----|-----|-----|
 "" |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 A  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 B  |  0  |  1  |  0  |  0  |  0  |  0  |  0  |
 C  |  0  |  0  |  2  |  0  |  0  |  0  |  0  |
 D  |  0  |  0  |  0  |  3  |  0  |  0  |  0  |
 E  |  0  |  0  |  0  |  0  |  4  |  0  |  0  |
 F  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |

步骤3: 找出最大值

遍历整个表格，找到最大值及其位置：

最大值是4，位于dp[5][4]，表示以s1[4]=’E’和s2[3]=’E’结尾的最长公共子串长度为4

步骤4: 提取最长公共子串

根据最大值的位置回溯：

结束位置：endIndex = 4（对应s1中的’E’）
起始位置：startIndex = endIndex - maxLength + 1 = 4 - 4 + 1 = 1（对应s1中的’B’）
最长公共子串：s1[1…4] = “BCDE”

在DP表格中，最长公共子串形成了一条沿对角线增长的”路径”：

    |  "" |  B  |  C  |  D  |  E  |  G  |  H  |
----|-----|-----|-----|-----|-----|-----|-----|
 "" |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 A  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
 B  |  0  |  1* |  0  |  0  |  0  |  0  |  0  |
 C  |  0  |  0  |  2* |  0  |  0  |  0  |  0  |
 D  |  0  |  0  |  0  |  3* |  0  |  0  |  0  |
 E  |  0  |  0  |  0  |  0  |  4* |  0  |  0  |
 F  |  0  |  0  |  0  |  0  |  0  |  0  |  0  |

这种对角线增长模式是最长公共子串问题的特征，每一步的增长都表示匹配的字符数增加了1。

4. 完整算法实现

下面是最长公共子串算法的完整Swift实现：

  
func longestCommonSubstring(_ s1: String, _ s2: String) -> String {
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    let m = chars1.count
    let n = chars2.count
    
    // 创建dp数组
    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
    
    // 记录最长子串的长度和结束位置
    var maxLength = 0
    var endIndex = 0
    
    // 填充dp数组
    for i in 1...m {
        for j in 1...n {
            if chars1[i-1] == chars2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                
                // 更新最长子串信息
                if dp[i][j] > maxLength {
                    maxLength = dp[i][j]
                    endIndex = i - 1
                }
            }
        }
    }
    
    // 如果没有公共子串
    if maxLength == 0 {
        return ""
    }
    
    // 从原字符串中提取最长公共子串
    let startIndex = endIndex - maxLength + 1
    return String(chars1[startIndex...endIndex])
}

// 测试代码
let s1 = "ABCDEF"
let s2 = "BCDEGH"
let result = longestCommonSubstring(s1, s2)
print("最长公共子串: \(result)") // 输出: "BCDE"

5. 空间优化

标准动态规划方法需要O(m*n)的空间复杂度。通过观察状态转移方程，我们发现每次计算dp[i][j]时只依赖于dp[i-1][j-1]，因此可以优化空间使用：

  
func longestCommonSubstringOptimized(_ s1: String, _ s2: String) -> String {
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    let m = chars1.count
    let n = chars2.count
    
    // 使用一维数组
    var dp = Array(repeating: 0, count: n + 1)
    
    var maxLength = 0
    var endIndex = 0
    
    for i in 1...m {
        // 从后向前遍历以避免覆盖尚未使用的旧值
        for j in stride(from: n, through: 1, by: -1) {
            if chars1[i-1] == chars2[j-1] {
                dp[j] = dp[j-1] + 1
                
                if dp[j] > maxLength {
                    maxLength = dp[j]
                    endIndex = i - 1
                }
            } else {
                dp[j] = 0
            }
        }
    }
    
    if maxLength == 0 {
        return ""
    }
    
    let startIndex = endIndex - maxLength + 1
    return String(chars1[startIndex...endIndex])
}

通过这种优化，空间复杂度从O(m*n)降低到O(n)，其中n是较短字符串的长度。这种优化在处理大规模数据时尤为重要。

6. 复杂度分析

时间复杂度：O(m×n)，需要填充m×n大小的表格
空间复杂度：
- 标准实现：O(m×n)，需要存储整个DP表格
- 优化版本：O(min(m,n))，只需存储一行/一列

动态规划是解决最长公共子串问题的最常用方法，它清晰地展示了问题的结构，并提供了可扩展的解决方案框架，使其能够应用于各种变体问题。

四、经典问题与变体

最长公共子串算法在实际应用中有多种变体和扩展，下面介绍几种常见的相关问题。

1. 两个字符串的最长公共子串

这是最基本的问题形式，前面已经详细讨论。它的核心是找出两个字符串中最长的连续公共部分。

相关LeetCode题目:

718. 最长重复子数组 - 实质上就是求两个数组的最长公共子数组，与最长公共子串思路相同

示例:

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]，相当于找出"12321"和"32147"的最长公共子串"321"

解题思路图解：

对于数组 [1,2,3,2,1] 和 [3,2,1,4,7]，使用动态规划构建的DP表格如下：

DP表格:
3  2  1  4  7
 0  0  0  0  0  0
 0  0  0  1  0  0
 0  0  1  0  0  0
 0  1  0  0  0  0
 0  0  2  0  0  0
 0  0  0  3  0  0

通过表格可以清晰地看出，最长公共子数组的长度为3，对应子数组 [3,2,1]。

2. 多个字符串的最长公共子串

问题描述：给定k个字符串，找出它们的最长公共子串。

解法：

动态规划扩展：理论上可以扩展到k维状态数组，但在实际应用中不实用，因为空间和时间复杂度都会随着字符串数量的增加呈指数级增长
后缀数组：对于多字符串问题，后缀数组是更适合的解决方案
分治法：先找出前两个字符串的最长公共子串，再与第三个字符串比较，以此类推

Swift实现：

  
func longestCommonSubstringOfMultiple(_ strings: [String]) -> String {
    guard !strings.isEmpty else { return "" }
    if strings.count == 1 { return strings[0] }
    
    var result = strings[0]
    
    for i in 1..<strings.count {
        result = longestCommonSubstring(result, strings[i])
        if result.isEmpty {
            return ""  // 如果某一步结果为空，说明不存在公共子串
        }
    }
    
    return result
}

// 使用示例
let multipleStrings = ["ABABC", "BABCA", "ABCBA"]
let multipleResult = longestCommonSubstringOfMultiple(multipleStrings)
// 结果: "AB"，因为"AB"是唯一同时出现在所有三个字符串中的连续子串

算法复杂度：

时间复杂度：O(n²k)，其中n是字符串的平均长度，k是字符串的数量
空间复杂度：O(n²)

3. 字符串中最长的重复子串

问题描述：在一个字符串中，找出最长的重复子串（该子串在字符串中至少出现两次）。

相关LeetCode题目:

1044. 最长重复子串 - 需要使用后缀数组或二分查找+哈希的方法

示例:

输入："banana"
输出："ana"
解释："ana"在字符串中出现了两次，是最长的重复子串

示例2:

输入："abcd"
输出：""
解释：没有重复出现的子串

后缀数组解法：

  
func longestDuplicateSubstring(_ s: String) -> String {
    let chars = Array(s)
    let n = chars.count
    
    // 创建所有后缀
    var suffixes = [(Int, [Character])]()
    for i in 0..<n {
        suffixes.append((i, Array(chars[i..<n])))
    }
    
    // 按字典序排序
    suffixes.sort { $0.1.lexicographicallyPrecedes($1.1) }
    
    var maxLength = 0
    var resultStart = 0
    
    // 计算相邻后缀的最长公共前缀(LCP)
    for i in 0..<n-1 {
        let length = lcp(suffixes[i].1, suffixes[i+1].1)
        if length > maxLength {
            maxLength = length
            resultStart = suffixes[i].0
        }
    }
    
    if maxLength == 0 {
        return ""
    }
    
    return String(chars[resultStart..<(resultStart + maxLength)])
}

// 计算最长公共前缀
func lcp(_ s1: [Character], _ s2: [Character]) -> Int {
    let minLength = min(s1.count, s2.count)
    for i in 0..<minLength {
        if s1[i] != s2[i] {
            return i
        }
    }
    return minLength
}

算法复杂度：

时间复杂度：O(n²log n)，排序需要O(n log n)，比较需要O(n²)
空间复杂度：O(n²)，存储所有后缀

4. 带有差异的最长公共子串

问题描述：找出两个字符串的最长公共子串，允许最多k个字符不同。

相关LeetCode题目:

1062. 最长重复子串 - 与上面的1044类似
395. 至少有K个重复字符的最长子串 - 虽然不是直接的变体，但解法思路类似

示例 (395题):

输入：s = "aaabb", k = 3
输出：3
解释：最长子串是 "aaa"，因为'a'重复了3次，满足至少出现k=3次的条件

动态规划解法（允许k个差异）：

  
func longestCommonSubstringWithDifferences(_ s1: String, _ s2: String, _ k: Int) -> String {
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    let m = chars1.count
    let n = chars2.count
    
    // dp[i][j][d] 表示以s1[i-1]和s2[j-1]结尾，有d个差异的最长公共子串长度
    var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: k+1), count: n+1), count: m+1)
    
    var maxLength = 0
    var endIndex = 0
    
    for i in 1...m {
        for j in 1...n {
            // 字符相同的情况
            if chars1[i-1] == chars2[j-1] {
                for d in 0...k {
                    if d == 0 {
                        dp[i][j][d] = dp[i-1][j-1][d] + 1
                    } else {
                        dp[i][j][d] = dp[i-1][j-1][d] + 1
                    }
                    
                    if dp[i][j][d] > maxLength {
                        maxLength = dp[i][j][d]
                        endIndex = i - 1
                    }
                }
            } else {
                // 字符不同的情况
                for d in 1...k {
                    dp[i][j][d] = dp[i-1][j-1][d-1] + 1
                    
                    if dp[i][j][d] > maxLength {
                        maxLength = dp[i][j][d]
                        endIndex = i - 1
                    }
                }
            }
        }
    }
    
    if maxLength == 0 {
        return ""
    }
    
    let startIndex = endIndex - maxLength + 1
    return String(chars1[startIndex...endIndex])
}

算法复杂度：

时间复杂度：O(mnk)，其中m和n是两个字符串的长度，k是允许的差异数
空间复杂度：O(mnk)

五、算法优化与实践建议

处理最长公共子串问题时，根据具体应用场景和数据规模，可以采用不同的优化策略。

1. 性能优化技巧

a) 优先处理短字符串

当两个字符串长度差异大时，将较短的字符串作为参考可以减少内存使用和提高效率：

  
func longestCommonSubstringOptimizedForLength(_ s1: String, _ s2: String) -> String {
    // 确保s1是较短的字符串
    if s1.count > s2.count {
        return longestCommonSubstringOptimizedForLength(s2, s1)
    }
    
    // 以下是标准的动态规划实现...
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    // ...省略相同的实现逻辑
}

这种优化在处理长度悬殊的字符串时特别有效，如将一个短字符串与基因组数据比较。

b) 使用哈希加速比较

对于长字符串，可以使用哈希技术加速子串比较，减少直接字符比较的次数：

  
func findSubstringWithHash(_ s1: String, _ s2: String, _ length: Int) -> String? {
    if length == 0 { return "" }
    if length > s1.count || length > s2.count { return nil }
    
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    let prime = 101
    let mod = 1_000_000_007
    
    // 计算字符串哈希
    func calculateHash(_ chars: [Character], _ start: Int, _ length: Int) -> Int {
        var hash = 0
        for i in 0..<length {
            hash = (hash * prime + Int(chars[start + i].asciiValue!)) % mod
        }
        return hash
    }
    
    // 构建s1的所有长度为length的子串的哈希值
    var s1Hashes = [Int: [Int]]()
    for i in 0...(chars1.count - length) {
        let hash = calculateHash(chars1, i, length)
        s1Hashes[hash, default: []].append(i)
    }
    
    // 检查s2中的子串是否在s1中出现
    for i in 0...(chars2.count - length) {
        let hash = calculateHash(chars2, i, length)
        if let positions = s1Hashes[hash] {
            for pos in positions {
                // 验证子串是否真的相同（避免哈希冲突）
                if String(chars1[pos..<(pos + length)]) == String(chars2[i..<(i + length)]) {
                    return String(chars2[i..<(i + length)])
                }
            }
        }
    }
    
    return nil
}

哈希方法特别适合比较大量子串，尤其是在文本搜索和分析中。

c) 二分查找加速

当我们需要找到特定长度的公共子串时，可以结合二分查找和哈希技术：

  
func longestCommonSubstringWithBinarySearch(_ s1: String, _ s2: String) -> String {
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    
    var left = 0
    var right = min(chars1.count, chars2.count)
    var result = ""
    
    while left <= right {
        let mid = (left + right) / 2
        
        if let common = findSubstringWithHash(s1, s2, mid) {
            // 如果找到长度为mid的公共子串，尝试找更长的
            result = common
            left = mid + 1
        } else {
            // 否则，缩小搜索范围
            right = mid - 1
        }
    }
    
    return result
}

该方法的时间复杂度为O((m+n) log min(m,n))，在处理较长的字符串时比传统动态规划更高效。

2. 大规模数据的处理建议

对于超大规模数据，标准算法可能会遇到性能瓶颈，以下是处理建议：

流式处理：不要一次性加载所有数据到内存，而是采用分段处理

  
func processLargeStrings(file1: String, file2: String, chunkSize: Int) {
    // 分块读取文件并处理
}

分块处理：将大字符串分成小块处理，再合并结果

  
func divideAndConquer(_ s1: String, _ s2: String, _ maxChunkSize: Int) -> String {
    // 将字符串分割成较小的块，分别处理
}

并行计算：利用多核处理器并行计算不同部分

  
func parallelProcess(_ s1: String, _ s2: String) {
    let queue = DispatchQueue(label: "com.example.lcs", attributes: .concurrent)
    // 实现并行计算逻辑
}

外部存储：对于超大数据集，考虑使用数据库或外部存储来辅助计算
近似算法：在某些场景下，可以考虑使用近似算法，牺牲一定精度换取性能提升

3. 常见错误与陷阱

在实现最长公共子串算法时，应当注意以下常见问题：

索引处理错误：动态规划中的索引偏移容易出错，特别是在使用0-索引和1-索引的转换时

  
// 常见错误
if chars1[i] == chars2[j] { // 应该是chars1[i-1] == chars2[j-1]
    dp[i][j] = dp[i-1][j-1] + 1
}

空字符串处理：确保算法能正确处理空字符串输入
1 guard !s1.isEmpty && !s2.isEmpty else { return "" }
长度为1的公共子串：有些实现可能会忽略长度为1的公共子串
1 2 // 确保maxLength的初始值为0，而不是1 var maxLength = 0

多个最长子串：如果有多个相同长度的最长公共子串，需要明确处理策略

  
// 可以选择记录所有的最长公共子串
var allLongestSubstrings = [String]()

Unicode处理：在处理包含特殊字符的字符串时，需要正确处理Unicode编码

  
// 使用Unicode感知的方法处理字符串
let normalizedS1 = s1.precomposedStringWithCanonicalMapping

溢出处理：处理大字符串时要防止哈希值溢出

  
// 使用模运算防止溢出
hash = (hash * prime + charValue) % mod

六、总结

1. 算法比较

针对最长公共子串问题，我们讨论了几种不同的解决方法，下表总结了它们的性能特点和适用场景：

算法	时间复杂度	空间复杂度	适用场景
朴素方法	O(n³)	O(1)	短字符串、教学演示
动态规划	O(m*n)	O(m*n)	通用场景、中等长度字符串
空间优化DP	O(m*n)	O(min(m,n))	内存受限环境
后缀数组	O(n log n)	O(n)	长字符串、多字符串比较
哈希+二分	O((m+n) log min(m,n))	O(m)	长字符串、特定长度搜索
滑动窗口	O(m*n)	O(1)	短到中等长度字符串

算法性能对比分析：

不同算法在处理不同规模数据时的表现存在显著差异。对于较短的字符串（长度<100），各种方法的性能差异不明显，但随着字符串长度增加，差异会迅速扩大：

朴素方法：在字符串长度超过1000时性能急剧下降
动态规划：在处理10,000长度的字符串时仍能保持可接受的性能
后缀数组：在处理100,000级别的字符串时表现出色
哈希+二分查找：适合快速确定是否存在特定长度的公共子串

算法

算法动态规划字符串子串最长公共子串后缀数组

本文由作者按照 CC BY 4.0 进行授权

一、基本概念

1. 什么是最长公共子串？

2. 最长公共子串与最长公共子序列的区别

3. 为什么需要研究最长公共子串？

二、最长公共子串的算法原理

1. 朴素方法

2. 动态规划方法

3. 后缀数组方法

4. 滑动窗口方法

三、动态规划解法详解

1. 状态定义

2. 状态转移方程

3. 动态规划过程可视化

4. 完整算法实现

5. 空间优化

6. 复杂度分析

四、经典问题与变体

1. 两个字符串的最长公共子串

2. 多个字符串的最长公共子串

3. 字符串中最长的重复子串

4. 带有差异的最长公共子串

五、算法优化与实践建议

1. 性能优化技巧

a) 优先处理短字符串

b) 使用哈希加速比较

c) 二分查找加速

2. 大规模数据的处理建议

3. 常见错误与陷阱

六、总结

1. 算法比较

热门标签