string - 最短公共(public)超序列

Question

问题是给定 2 个字符串 X 和 Y，我们需要找到最短序列 Z 的长度，这样两个字符串都作为 Z 中的子序列出现。现在，我的直觉是 length = |X| + |是| -|LCS(X,Y)|。但是我们如何证明呢？

例如:X = AGGTAB ，Y = GXTXAYB ，然后 Z = AGXGTXAYB 和 |Z| = 9 。 LCS(X,Y) = GTAB

引用:Link 1 Link 2

Answer 1

首先，查看您发送的第二个链接，可以创建一个大小为 |X| 的 super 序列+ |是| - |LCS(X,Y)|:

For two input sequences, an scs can be formed from a longest common subsequence (lcs) easily...

所以现在剩下的就是证明它实际上是最短公共(public)超序列。假设相反，假设存在一个最短公共(public)超序列使得它的长度为|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