打印超级序列

问题描述 投票:0回答:1

我正在努力理解两个给定字符串的最小超序列的概念。

我了解如何从解决两个给定字符串的 LCS 问题后得到的 2D dp 表中打印这个超序列。我不明白我们如何证明我们得到的输出确实是最小超序列。

我们需要证明这一点

  1. 它是最小的 - 我想这很明显,因为我们打印两个字符串的所有不同元素并且只打印一次 LCS 元素,没关系

  2. 这是一个超序列 - 我不明白为什么我们得到的输出结果保持了正确的超序列顺序

有人可以澄清一下吗?

string algorithm substring dynamic-programming
1个回答
0
投票

由于您除了提到它是 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 转换所做的就是对两个字符串的这些状态更新循环进行有效模拟。

© www.soinside.com 2019 - 2024. All rights reserved.