最短公共超序列

最短公共超序列是 Longest Common Subsequence（最长公共子序列）的变种。

问题陈述：给定两个字符串 s1 和 s2，返回一个最短的字符串，该字符串同时包含 s1 和 s2 作为子序列。如果存在多个答案，则可以返回其中任何一个。

(如果从字符串 T 中删除一些字符可以得到字符串 S，则称 S 是 T 的子序列)。

让我们通过一个例子来理解上面的陈述。

输入：str1 = "abac"

str2 = "cab"

输出

最短公共超序列将是 "cabac"。

说明

字符串 str1 = "abac" 是 cabac 的子序列，因为我们可以从字符串 "cabac" 中删除字母 'c'，得到 "abac"。

字符串 str2 = "cab" 是 "cabac" 的子序列，因为我们可以从字符串 "cabac" 中删除字母 'a' 和 'c'，得到 "cab"。

考虑有以下两个字符串的问题

S1: "abac"

S2: "cab"

问题的目标是找到最短公共超序列 (SCS)。在这里，超序列也是一个字符串，它保持了 S1 和 S2 的顺序。让我们将超序列视为 S3，这样当我们考虑字符串 S1 在 S3 中时，它就变成了 S3 的子序列。类似地，当我们考虑字符串 S2 在 S3 中时，它也变成了 S3 的子序列。

一种简单的超序列类型是我们将 S1 和 S2 两个字符串连接起来。

连接后，字符串将是

S3: abac cab

我们可以从上面的字符串中观察到，S1 和 S2 字符串是并排添加的。因此，我们可以说 S3 是一个超序列。我们可以形成更多的超序列。要形成任何子序列，我们可以在子序列之间添加字符，但顺序必须相同。另一种超序列形式可以生成为

S3: abcacab

在上面的超序列中，我们首先将字符串 S1 的 "ab" 添加到 S3 中，然后我们将 'c' 添加到 S3 中，我们添加 S1 的 "ac"，然后添加 S2 的 "ab" 到 S3 中。

第三种形式的超序列如下所示

S3: abcab

上面的字符串也是一个超序列。当我们比较 S1 和 S3 时，我们发现字符串 S1 在 S3 中是子序列。类似地，当我们比较 S2 和 S3 时，我们发现字符串 S2 在 S3 中是子序列。由于字符 'c' 在两个字符串中是公共的；与其将字母 'c' 写两次，不如只写一次 'c'。这导致超序列的长度缩短。超序列的长度为 5。

第四种形式的超序列如下所示

S3: cabac

上面的字符串也是一个超序列。当我们比较 S1 和 S2 字符串与 S3 时，我们发现两个字符串都作为子序列包含在字符串 S3 中。由于两个字符串都作为子序列包含在字符串 S3 中；因此，我们可以说 S3 是这两个字符串的超序列。超序列的长度为 5，它是最短的超序列。因此，最短公共超序列是 "cabac"。

如何找到超序列的长度？

在最坏的情况下，超序列的长度 = (L1 + L2) = 7。我们需要遵循以下规则来减小超序列的长度

• 我们可以匹配一些重叠的字符，形成一个较短的超序列。
• 为了形成最短的超序列，我们需要取最长的重叠字符。

如果我们只考虑一个公共字符，即 'c'，那么我们将只在超序列中添加一个 'c'，如下所示

S3: abacab

如果我们考虑字符串 S1 和 S2 之间的最长公共子序列，即 'ab'，那么我们将只在超序列中添加一个 'ab'，而不是写两次

S3: cabac

因此，

最短公共超序列的长度 = (L1 + L2) - LCS

在上面的例子中，

L1 = 4

L2 = 3

LCS = 2 ('ab' 出现两次)

最短公共超序列的长度 = (4 + 3) - 2

= 7-2 = 5

示例 2：考虑以下两个字符串

S1: AGGTAB

S2: GXTXAXB

当我们比较 S1 和 S2 这两个字符串时，我们发现最长公共子序列等于 GTAB。

S1 的长度 = 6

S2 的长度 = 7

因此，最短公共超序列的长度 = (6 + 7) - 4 = 9

如何找到 SCS 字符串？

考虑以下两个字符串

S1: A G G T A B

S2: G X T X A Y B

首先，我们将找到 LCS 字符串，它得到

LCS: G T A B

一旦 LCS 字符串计算完毕，我们将找出 SCS 字符串，正如我们已经讨论过的，LCS 字符串中的字符在 SCS 字符串中应该只出现一次。

在创建 LCS 字符串时，我们需要记住以下几点

• LCS 字符只添加一次。
• 假设第一个公共字符属于 LCS 字符。
• 按照 S1 然后 S2 或反之的顺序添加非 LCS 字符。

我们将从左到右遍历字符串。任何同时出现在两个字符串中的公共字符，然后我们将该字符包含在 LCS 的开头。现在我们将进行一次干运行以更清楚地理解。

考虑指向字符串 S1 的指针 P1，指向字符串 S2 的指针 P2，以及指向 LCS 字符串的指针 P3。

最初，P1 指针指向 S1 的字符 'A'，P3 指向字符 'G'。由于两个字符都不同，我们将字符 'A' 包含在 SCS 字符串中，如下所示

SCS: "A"

一旦字符 'A' 被包含在 SCS 字符串中，我们将增加 P1 指针，使其指向字符 'G'。现在比较 P2 在 S2 中指向的字符与 P3 指向的字符。由于两个字符，即 'G' 相同，所以我们不包含 'G'。由于字符 'G' 在 S1、S2 和 LCS 中是公共的，我们将字符 'G' 包含在 SCS 字符串中，如下所示

SCS: "AG"

一旦字符 'G' 被包含在 SCS 字符串中，我们将增加 P1、P2 和 P3 指针。现在 P1 指向 'G'，P2 指向 X，P3 指向 T。

比较 P1 和 P3；由于 'G' 和 'T' 是不同的，所以我们将 'G' 包含在 SCS 字符串中并增加 P1 指针，如下所示

SCS: "AGG"

比较 P1 和 P3；由于两个字符都相同，即 T，所以我们在这里停止。比较 P2 和 P3；由于字符 'X' 和 'T' 不同，所以我们将 'X' 包含在 SCS 字符串中并增加 P2 指针，如下所示

SCS: "AGGX"

再次比较 P2 和 P3；由于字符 'T' 在 S1、S2 和 LCS 中是公共的，所以我们只包含一次 'T' 在 SCS 中，如下所示

SCS: "AGGXT"

一旦字符 'T' 被包含在 SCS 字符串中，我们将增加 P1、P2 和 P3 指针。现在 P1 指向 'A'，P2 指向 X，P3 指向 A。

比较 P1 和 P3；由于字符相同，即 A，所以我们在这里停止。比较 P2 和 P3；字符 'X' 和 'A' 不同，所以我们将 X 包含在 SCS 字符串中并增加 P2 指针，如下所示

SCS: "AGGXTX"

现在 P1、P2 和 P3 指针指向的字符相同，即 A，所以我们将字符 'A' 包含在 SCS 字符串中，如下所示

SCS: "AGGXTXA"

一旦字符 'A' 被包含在 SCS 字符串中，我们将增加 P1、P2 和 P3 指针。现在 P1 指向 'B'，P2 指向 Y，P3 指向 B。比较 P1 和 P3；由于字符相同，所以我们在这里停止。

比较 P2 和 P3 指针；由于字符不同，所以我们将 'Y' 添加到 SCS 字符串中并增加指针，如下所示

SCS: "AGGXTXAY"

现在 P1、P2 和 P3 指针指向的字符相同，即 B，所以我们将字符 'B' 包含在 SCS 字符串中，如下所示

SCS: "AGGXTXAYB"

C 语言实现

输出