我正在努力理解两个给定字符串的最小超序列的概念。
我了解如何从解决两个给定字符串的 LCS 问题后得到的 2D dp 表中打印这个超序列。我不明白我们如何证明我们得到的输出确实是最小超序列。
我们需要证明这一点
它是最小的 - 我想这很明显,因为我们打印两个字符串的所有不同元素并且只打印一次 LCS 元素,没关系
这是一个超序列 - 我不明白为什么我们得到的输出结果保持了正确的超序列顺序
有人可以澄清一下吗?
由于您除了提到它是 DP 表之外没有指定确切的算法,所以我将从头开始。考虑一个检查 S 是否是 T 的子序列的过程:
check(S, T):
state = 0
if length(S) == 0: return true
for char c in T:
if S[state] == c: state++
if length(S) == state: return true
return false
这里的内部
state
是S的最长前缀的长度,可以作为当前处理的T的前缀的子序列找到。应该很明显为什么这是正确的。
有了 2 个字符串
(S1, S2)
,我们就有了状态对 (state1, state2)
,动态规划就变成了:T 的最短可能前缀是什么,这样当我们在这 2 个字符串上独立运行时,上面的过程就会得到这些状态值?与列出给定长度的所有可能字符串并为每个字符串计算这对状态相比,DP 仅使用了两个优化思想:
dp[state1][state2]
中找到任何先前状态的 (prev_state1, prev_state2)
,我们只需要给出 (prev_state1, prev_state2)
的 T 的最短前缀,即 dp[prev_state1][prev_state2]
,因为(看 check(S, T)
)下一个状态不依赖于 T 前缀的前一部分,仅依赖于之前的状态和要添加的字符c
是S1[state1]
和S2[state2]
,因为其他任何字符都会给出更长的相同状态最后,
dp[length(S1)][length(S2)]
给出最短的前缀,即最短的超串T,两个检查(Sx是T的子序列)都为真。 DP 转换所做的就是对两个字符串的这些状态更新循环进行有效模拟。