最短公共超序列

一句话套路:最短超序列 = 把 LCS 当骨架,公共字符只写一次、独有字符按原序补入。先填 dp 表求 LCS,再沿表重构。

先搭骨架:行对应 str1「abac」的字符,列对应 str2「cab」的字符,行列末尾各加一格 ∅ 代表「空后缀」。dp[i][j] 表示 str1 第 i 个起的后缀 与 str2 第 j 个起的后缀 的 LCS 长度,现在全是「·」表示还没算。我们从右下往左上填。

最下面一行是 str1 的空后缀:空串和任何串的 LCS 都是 0,整行填 0(紫格)。它是后面所有格往下看时的地基。

最右边一列是 str2 的空后缀:同理 LCS 都是 0,整列填 0(紫格)。基础格备齐,接下来从右下角内部一格格往左上推。

看 "c" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[4][2]=0(跳过 str1 这个字符),右方 dp[3][3]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "c" 和 "a":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[4][1]=0(跳过 str1 这个字符),右方 dp[3][2]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "c"(str1 第 4 个)和 "c"(str2 第 1 个):相同!这个字符能进 LCS,长度 = 右下角 dp[4][1]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。

看 "a" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[3][2]=0(跳过 str1 这个字符),右方 dp[2][3]=0(跳过 str2 这个字符),取较大 = 0(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "a"(str1 第 3 个)和 "a"(str2 第 2 个):相同!这个字符能进 LCS,长度 = 右下角 dp[3][2]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。

看 "a" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[3][0]=1(跳过 str1 这个字符),右方 dp[2][1]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "b"(str1 第 2 个)和 "b"(str2 第 3 个):相同!这个字符能进 LCS,长度 = 右下角 dp[2][3]=0 再加 1 = 1(紫格,蓝格是它依赖的右下角)。

看 "b" 和 "a":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[2][1]=1(跳过 str1 这个字符),右方 dp[1][2]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "b" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[2][0]=1(跳过 str1 这个字符),右方 dp[1][1]=1(跳过 str2 这个字符),取较大 = 1(下方与右方一样长,任选一边都对,这里固定优先取下方,蓝格是两个依赖)。

看 "a" 和 "b":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[1][2]=1(跳过 str1 这个字符),右方 dp[0][3]=0(跳过 str2 这个字符),取较大 = 1(下方更长,蓝格是两个依赖)。

看 "a"(str1 第 1 个)和 "a"(str2 第 2 个):相同!这个字符能进 LCS,长度 = 右下角 dp[1][2]=1 再加 1 = 2(紫格,蓝格是它依赖的右下角)。

看 "a" 和 "c":不同,当前这对没法同时进 LCS,只能跳过其中一个,看哪边后续 LCS 更长。下方 dp[1][0]=1(跳过 str1 这个字符),右方 dp[0][1]=2(跳过 str2 这个字符),取较大 = 2(右方更长,蓝格是两个依赖)。

整张表填满。左上角 dp[0][0] = 2,意思是 "abac" 与 "cab" 的最长公共子序列长度为 2(正是 "ab")。LCS 这副骨架有了,下面沿着 dp 表从左上角走一遍,把答案重构出来。

重构规则:站在格子 (i, j),① 若 str1[i]=str2[j],这是公共字符,只写一次,i、j 同时右下移;② 若不同,跟着「LCS 更长」的那一边走,把被跳过那一侧的独有字符先写进答案。指针从 (0,0) 出发。

当前 (0,0):"a" 与 "c" 不同。右方 LCS 2 更大,跟着右方走,要跳过 str2 的 "c",把这个 str2 独有字符先补进答案,只 j++(蓝格往右)。答案现在是 "c"。

当前 (0,1):"a" 两边相同,是公共字符,只写一次 "a" 进答案,然后 i、j 一起往右下走(绿格表示已落定)。答案现在是 "ca"。

当前 (1,2):"b" 两边相同,是公共字符,只写一次 "b" 进答案,然后 i、j 一起往右下走(绿格表示已落定)。答案现在是 "cab"。

指针有一边走到了头(到了 ∅ 边界),剩下另一边的字符不会再有公共部分,原样全部接上即可。这里 str1 还剩 "ac"、str2 还剩 "空",接上后答案 = "cabac"。

复盘:LCS "ab" 是公共骨架只写一次,str2 独有的 "c" 在前面补、str1 独有的 "ac" 在后面补,拼成 "cabac"。验证一下:从它里能跳取出 "abac"(原 str1)和 "cab"(原 str2),且长度 = str1 长 4 + str2 长 3 − LCS 长 2 = 5,无法更短。

边界:相同则原串;无公共则拼接;一方是另一方子序列则取较长串。

两个追问:重构要随机查表所以省不了空间;平手时任选一边都对、固定一个方向即可。