viv Blog
0%

面试知识整理(1)

发表于 分类于

算法题

【最长公共子串】 vs 【最长公共子序列】

考察动态规划知识；

区分：如果题目强调 “连续” → 子串；如果说 “顺序不变，可删除字符” → 子序列

  1. 最长公共子串（Substring）
    使用 动态规划，dp[i][j] 表示以 A[i-1] 和 B[j-1] 结尾的公共子串长度
    只有当 A[i-1] == B[j-1] 时，才能延续之前的匹配：
    dp[i][j] = dp[i-1][j-1] + 1
    否则 dp[i][j] = 0（因为不连续就断了）
1
2
3
4
5
6
7
8
9
10
11
12
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
end_pos = 0
for i in range(1, m+1):
    for j in range(1, n+1):
        if A[i-1] == B[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            if dp[i][j] > max_len:
                max_len = dp[i][j]
                end_pos = i
        else:
            dp[i][j] = 0  # 关键！不连续就归零
  1. 最长公共子序列（Subsequence）
    ✅ 核心思想：
    dp[i][j] 表示 A[:i] 和 B[:j] 的 LCS 长度
    转移方程：
1
2
3
4
if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
维度 最长公共子串 最长公共子序列
连续性 必须连续 不必连续
DP 状态含义 以 i,j 结尾的连续匹配长度 前 i,j 个字符的最优解
不匹配时处理 dp[i][j] = 0（断开） dp[i][j] = max(上, 左)（继承）
结果位置 需记录结束位置以回溯子串 通常只需长度，回溯较复杂
最大长度 ≤ min(len(A), len(B)) 可接近 min(len(A), len(B))，甚至等于
应用场景 文本相似片段检测、DNA 序列局部匹配 编辑距离、版本 diff、生物序列比对