最短公共超序列
Shortest common SuperSequence
问题是给定 2 个字符串 X 和 Y，我们需要找到最短序列 Z 的长度，这样两个字符串都作为 Z 中的子序列出现。现在，我的直觉是 length = |X| + |是| -|LCS(X,Y)|。但是我们如何证明呢？
例如：X = AGGTAB ，Y = GXTXAYB ，然后 Z = AGXGTXAYB 和 |Z| = 9 。 LCS(X,Y) = GTAB
首先，查看您发送的第二个 link，可以创建一个大小为 |X| 的超级序列+ |是| - |LCS(X,Y)|:
For two input sequences, an scs can be formed from a longest common subsequence (lcs) easily...
所以现在剩下的就是证明它实际上是最短公共超序列。假设相反，假设存在一个最短公共超序列使得它的长度为|X| + |是| - |LCS(X,Y)| - 1 == |X| + |是| - (|LCS(X,Y)| + 1)。但是在这个字符串中，你有 X 作为子序列，Y 作为子序列。这意味着它们相交于 |LCS(X,Y)| + 1 根据字符串的大小判断位置。那就是有一个大小为 |LCS(X,Y)| 的 LCS + 1，与LCS的定义矛盾！
因此，大小正好是|X| + |是| - |LCS(X,Y)|。 q.e.d
由于您只关心字母的个数，因此您可以对所有序列（X, Y, Z 和 LCS(X,Y) ）进行排序。这是因为排序序列（在计算出最小包含一个和 LCS 之后）将使字母的计数保持不变。
如果你正在考虑排序序列，你只需要考虑由 1 个字母组成的序列。这是因为每个序列中每个字母的计数独立于每个序列中所有其他字母的计数。
现在，如果您考虑仅由一个字母组成的序列，那么很明显，同时包含 X 和 Y 作为子序列的最小序列将是 X 或 Y，而 LCS(X,Y) 将是另一个。所以（为最小包含序列调整符号 "MCS"），|MCS(X,Y)| + |LCS(X,Y)| = |X| + |Y|.
设 
为字符串 1，
为字符串 2。
令S为由X和Y作为序列组成的任意最短超序列。让我们尝试创建这样一个序列。
显然，X作为序列存在于S中。因此，最初S可以表示为：
注意：'...'表示该位置可以为空，也可以用来将Y的字符放入其中，使其成为由X和Y组成的最短超序列。
现在，这个|S|必须是最小的。我们只需要将 Y 中的最少字符注入到此 S 中，使其成为由 X 和 Y 组成的最短超序列。另外，请注意条件是 Y 需要作为子序列而不是子字符串出现。因此，如果我发现 Y 的任何字符序列也出现在 X 中，则不需要注入 Y 的那些字符。
因此，对于 |S|为了最小化，我们展示了需要注入 Y 的最少字符，以便 Y 作为序列出现。为此，我们找到最长的 X 序列也出现在 Y 中，换句话说 = LCS(X,Y).
|S| = |X| + ( |Y| - |LCS(X,Y)| ) = |X| +|是| - |LCS(X,Y)|
现在，存在多个LCS(X,Y)。取任意一个并构建序列。
问题是给定 2 个字符串 X 和 Y，我们需要找到最短序列 Z 的长度，这样两个字符串都作为 Z 中的子序列出现。现在，我的直觉是 length = |X| + |是| -|LCS(X,Y)|。但是我们如何证明呢？
例如：X = AGGTAB ，Y = GXTXAYB ，然后 Z = AGXGTXAYB 和 |Z| = 9 。 LCS(X,Y) = GTAB
首先，查看您发送的第二个 link，可以创建一个大小为 |X| 的超级序列+ |是| - |LCS(X,Y)|:
For two input sequences, an scs can be formed from a longest common subsequence (lcs) easily...
所以现在剩下的就是证明它实际上是最短公共超序列。假设相反，假设存在一个最短公共超序列使得它的长度为|X| + |是| - |LCS(X,Y)| - 1 == |X| + |是| - (|LCS(X,Y)| + 1)。但是在这个字符串中，你有 X 作为子序列，Y 作为子序列。这意味着它们相交于 |LCS(X,Y)| + 1 根据字符串的大小判断位置。那就是有一个大小为 |LCS(X,Y)| 的 LCS + 1，与LCS的定义矛盾！
因此，大小正好是|X| + |是| - |LCS(X,Y)|。 q.e.d
由于您只关心字母的个数，因此您可以对所有序列（X, Y, Z 和 LCS(X,Y) ）进行排序。这是因为排序序列（在计算出最小包含一个和 LCS 之后）将使字母的计数保持不变。
如果你正在考虑排序序列，你只需要考虑由 1 个字母组成的序列。这是因为每个序列中每个字母的计数独立于每个序列中所有其他字母的计数。
现在，如果您考虑仅由一个字母组成的序列，那么很明显，同时包含 X 和 Y 作为子序列的最小序列将是 X 或 Y，而 LCS(X,Y) 将是另一个。所以（为最小包含序列调整符号 "MCS"），|MCS(X,Y)| + |LCS(X,Y)| = |X| + |Y|.
设 为字符串 1，
为字符串 2。
令S为由X和Y作为序列组成的任意最短超序列。让我们尝试创建这样一个序列。
显然，X作为序列存在于S中。因此，最初S可以表示为：
注意：'...'表示该位置可以为空，也可以用来将Y的字符放入其中，使其成为由X和Y组成的最短超序列。
现在，这个|S|必须是最小的。我们只需要将 Y 中的最少字符注入到此 S 中，使其成为由 X 和 Y 组成的最短超序列。另外，请注意条件是 Y 需要作为子序列而不是子字符串出现。因此，如果我发现 Y 的任何字符序列也出现在 X 中，则不需要注入 Y 的那些字符。
因此，对于 |S|为了最小化，我们展示了需要注入 Y 的最少字符，以便 Y 作为序列出现。为此，我们找到最长的 X 序列也出现在 Y 中，换句话说 = LCS(X,Y).
|S| = |X| + ( |Y| - |LCS(X,Y)| ) = |X| +|是| - |LCS(X,Y)|
现在，存在多个LCS(X,Y)。取任意一个并构建序列。