题目
给定两个字符串，求
最长公共连续子序列的长度，允许其中出现
最多一处"错误"——也就是两个子串按位对齐时，至多有一个位置的字符不相等，这一整段仍然算「公共的、连续的」。
s = "abcdef", t = "abcdxf"
只有 e / x 这一处不同，所以 6 个字符整体就算一段带 1 处错的公共连续子串
输出: 6
这题的现实场景很直白：DNA 序列比对（允许一个突变）、拼写纠错（允许一个错字）、日志对齐（允许一处噪声）。面试里它的地位类似「允许一次操作的最长公共子序列」——
考点不在 DP 本身，而在你有没有把状态分家。
一、先澄清题面：「连续」是子串，不是子序列
题面写「公共
连续子序列」，但这两个词在中文里经常混用，面试现场必须先钉死：
本系列之前写过「最长公共子序列」——那题允许跳格，转移里会出现
max(左, 上, 左上)。而本题
只走对角线，转移里只会出现左上角。把两者搞混是第一个坑：
一旦允许跳格，「连续」这个词就失效了，题目变成了另一道题。
二、双状态 DP：f 是干净的，g 才带额度
想清楚「至多一处错」意味着什么，就知道为什么一个状态不够：
- 想回答「以 s[i-1]、t[j-1] 结尾的这段，从头到尾一个错都没有能有多长」——这是一个状态；
- 想回答「同一位置结尾，至多一处错能有多长」——这是另一个状态。
后者可能在某个字符上已经用掉了唯一那次错误。如果它继续往左接，就可能
再消耗一次，配额就失效了。所以必须开两个状态，
干净的那个专供「接错误」时取用：
f[i][j] 以 s[i-1]、t[j-1] 结尾，全程字符相等的最长公共子串长度
g[i][j] 以 s[i-1]、t[j-1] 结尾，至多一处不等的最长公共子串长度
转移只有两条分支：
s[i-1] === t[j-1]:
f[i][j] = f[i-1][j-1] + 1
g[i][j] = g[i-1][j-1] + 1 # 相等，不消耗额度
s[i-1] !== t[j-1]:
f[i][j] = 0 # 断了，干净后缀清零
g[i][j] = max(f[i-1][j-1] + 1, 1) # 额度只能从 f 接
g[i][j] = max(f[i-1][j-1] + 1, 1) 这一行是整题的分水岭。 不等的时候，g 只能从
干净的 f 接过额度再 +1；如果写成
g[i-1][j-1] + 1，同一个字符就能反复消耗配额，答案一路虚涨（第九节有可执行反例）。
max(..., 1) 则保证「光这一格不相等」也算长度 1 的合法答案——两个毫无关系的字符之间，至少能凑出「一处错」。
def lcs1(s: str, t: str) -> int:
n, m = len(s), len(t)
f = [[0] * (m + 1) for _ in range(n + 1)]
g = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == t[j - 1]:
f[i][j] = f[i - 1][j - 1] + 1
g[i][j] = g[i - 1][j - 1] + 1
else:
f[i][j] = 0
g[i][j] = max(f[i - 1][j - 1] + 1, 1)
return max(max(row) for row in g) if n and m else 0
答案取
全表最大的 g。注意不是
g[n][m]——子串可以结束在任何一格。
三、动画怎么看
动画一（abcdef / abcdxf，8 帧） 演示双状态表格逐行填满。画面分四段：
- 横幅：当前行 / 当前动作（对角续上 · 不等断 f 接 g）/ 当前 best；
- 两串字符条：与表格列对齐，当前讲解格涉及的字符橙框标出；
- DP 表格：每格大数字是 g、左上角小数字是 f；当前行浅底、当前讲解格烫金、全表最优格绿色；
- 转移规则面板：把当前格的等式摊开写，比如「不等 → f 断成 0，g = f 左上 4 + 1 = 5（额度只能从 f 接）」。
值得盯的是第 6 帧（第 5 行，讲解格 (5, 5)）：
s[4]=e 对
t[4]=x 不等，
f 断成 0，而
g 从左上角的
f[4][4] = 4 接过额度再 +1，拿到 5 —— 这一格就是「额度从哪来」的唯一现场。
动画二（abcdef / bcdefa，13 帧） 把两条路径放在同一张小图上对照：正解走次对角线（
bcdef 格格全等，一路涨到 5），错法走主对角线（6 个位置格格不等，却因为误用 g 左上而一路涨到 6）。
四、完整推演表
主例
s = abcdef、
t = abcdxf，每行的 g 值（每行最大值）：
每行的最大值严格单调递增 1→6，答案 6 落在右下角
(6, 6)。
第 5 行是关键：讲解格
(5, 5) 上
f[5][5] = 0（e ≠ x，干净后缀断掉），
g[5][5] = f[4][4] + 1 = 4 + 1 = 5。
注意 f[4][4] = 4 而不是 g[4][4]——如果这里从 g 拿，这一格就会算成 5，往后第 6 行的答案跟着再虚高一截。
两个对照用例（同一个 bug 的不同体现）：
这两个反例不是编的：在 a/b/c 字母表、长度 0~4 的
全部 14641 组输入上穷举对拍，错法与正解在
61.8% 的输入上都给出不同答案。
五、空间优化：左上角必须单独存
g[i][j] 只依赖
g[i-1][j-1]，所以两行足够把空间压到
O(min(n, m))：
def lcs1_rolling(s: str, t: str) -> int:
if len(s) < len(t):
s, t = t, s # 让滚动维度取短边
f_prev = [0] * (len(t) + 1)
g_prev = [0] * (len(t) + 1)
best = 0
for i in range(1, len(s) + 1):
f_cur = [0] * (len(t) + 1)
g_cur = [0] * (len(t) + 1)
for j in range(1, len(t) + 1):
f_diag = f_prev[j - 1] # 左上角：必须在覆盖 prev 之前存下
g_diag = g_prev[j - 1]
if s[i - 1] == t[j - 1]:
f_cur[j] = f_diag + 1
g_cur[j] = g_diag + 1
else:
f_cur[j] = 0
g_cur[j] = max(f_diag + 1, 1)
best = max(best, g_cur[j])
f_prev, g_prev = f_cur, g_cur
return best
f_diag = f_prev[j - 1]：内层循环向右走，
f_prev[j - 1] 在被覆盖之前必须取出来；很多人在循环里直接写
f_prev[j - 1]，一旦把两行用同一个数组交替复用，左上角就变成了当前列的上一行值，答案悄悄错掉。这个错误不会崩、不会越界，只是答案偏小——最难查的一类 bug。
滚动版与二维版的一致性，我们做了穷举对拍：a/b/c 字母表、长度 0~5 的
132496 组输入，两版答案逐组一致。
六、实现要点与边界
- 答案是全表最大值，不是
g[n][m]：子串结束在任何一格；
- 空串返回 0（两个空串、单侧空串都要处理）；
- 两个毫无关系的字符答案是 1（
max(..., 1) 保证的），不是 0；
- 答案不超过较短串长度——所以可以对长串做预处理（取长度差之外的部分意义不大），或先剪掉不可能参与匹配的前后缀；
- 只回溯起点不够：如果面试官要「这段字符串本身」，还得在
g 达到最大值时回溯左上，直到 f == 0 的位置——回溯终点就是那一处错误所在。
七、追问：允许 k 处错误
把「一处」推广成「k 处」，状态从
g[i][j] 变成
g[i][j][e]（已用 e 次错误），转移照抄同一套逻辑：
s[i-1] === t[j-1]: g[i][j][e] = g[i-1][j-1][e] + 1 # 不消耗额度
s[i-1] !== t[j-1]: g[i][j][e] = g[i-1][j-1][e-1] + 1 # 从 e-1 那一档接过额度
g[i][j][0] = 0 # 0 次错误时不等就是断
——
e-1 档接过来，恰好保证同一格不重复消耗。k=0 时自然退化成最长公共子串。
额度放宽对答案的影响非常非线性，值得记两个实测：
第二行最典型：k=1 时答案还是 3，多给一处错误直接跳到 6（整串）。
所以 k 的选取不是「多给点总没坏处」——k 从 1 到 2 可能让答案翻倍，面试时值得主动点出这一点。
八、复杂度
1000 长度下，二维表 10^6 个 int 在 Java 里约 4 MB，能过；但 n、m 到 10^5 时表根本放不下，滚动数组也救不了时间（10^10 次运算），这时候就该换算法：位图 / 哈希分块 / SA-IS 之类的字符串工具（具体场景另开一篇）。
九、常见坑：五个每一个都能过样例
9.1 不等时误用 g[i-1][j-1]（本题头号 bug）
g[i][j] = g[i - 1][j - 1] + 1 # 错，应为 f[i-1][j-1] + 1
同一个字符上第二次消耗错误配额。反例
ab /
ba：正解 1，错法 2。穷举统计它与正解在 61.8% 的输入上都不同——
不是个别用例的边角问题，是整体性的错。
9.2 忘了 max(..., 1)
g[i][j] = f[i - 1][j - 1] + 1 # 错，缺了和 1 取最大
当左上角的
f 是 0（刚起头），这一格会算成 1 —— 对
a /
b 这种单字符恰好正确，但当整串都靠这一格起步时会把长度压低一格。保险写法是
max(f[i-1][j-1] + 1, 1)。
9.3 滚动数组没单独存左上角
两行数组交替复用时，
f_prev[j-1] 在被写入前必须取出；直接引用会在内层循环中被覆盖，答案静默偏小。这类 bug 不崩不越界，只能靠对拍发现。
9.4 把「连续」当「不连续」做
看到「子序列」就照 LCS 写，转移里出现
max(左, 上, 左上) —— 能跑，但算的是另一道题。
判据很简单：转移里一旦出现 左 或 上，就说明允许跳格了，题目已经不是这道。
9.5 以为「至多一处」=「恰好一处」
若把初始状态设成「必须用掉一次错误」（比如不等时不给长度 1 的机会），那么
abc /
abc 这种完全相同的输入会返回 0。题面写的是
至多，包含 0 次。
十、面试怎么答
30 秒版本：
两个状态。f[i][j] 是结尾相同且全程相等的最长公共子串长度，g[i][j] 是结尾相同、至多一处不等的长度。字符相等时两个状态都沿左上角 +1；不相等时 f 归 0，g = max(f 左上 + 1, 1) —— 额度只能从干净的 f 接，否则同一个字符会反复消耗配额。答案是全表最大的 g。时间 O(n × m)，滚动数组压到 O(min(n, m)) 空间。
如果还有时间，主动补三句，分别是三个加分点：
- 额度不变量：
g 只能从「更干净的档」接 —— 1 处错误版从 f 接，k 处错误版从 g[e-1] 接。这是全题唯一的核心思想；
- 滚动数组的陷阱：左上角必须在覆盖前取出，否则答案静默偏小；
- k 处错误的非线性：实测
abcdef / abxyef 在 k=1 时答案只有 3，k=2 直接跳到 6 —— k 不是「多给点总没坏处」。
这套题的完整状态机、渲染层和 26 个单测（穷举对拍 14641 组 + 滚动版 132496 组 + 1000 组随机对拍）都在仓库里，动画对应文章里的两个占位符。