最短的常见超序问题基本信息

在最短的通用超级序列是密切相关的最长公共子，你可以作为承担这一任务的外部功能使用上有问题。最短的共同超级序列问题是与最长公共子序列问题密切相关的问题。

最短的常见超序（scs）是最小长度的常见超序。在最短的共同超序列问题中，给出了两个序列 X 和 Y，并且任务是找到这些序列的最短可能的共同超序列。通常，scs 不是唯一的。

给定两个序列 X = <x1,...,xm> 和 Y = <y1,...,yn>，序列 U = <u1,...,uk> 是 X 和 Y 的共同超序列，如果 U 是 X 和 Y 的超级序列。换句话说，字符串 x 和 y 的最短公共超级序列是最短的字符串 z，使得 x 和 y 都是 z 的子序列。

对于两个输入序列，可以容易地从最长的公共子序列（lcs）形成 scs。例如，如果 X[1..m]=abcbdab 和 Y[1..n]=bdcaba，则 lcs 是 Z[1..r]=bcba。通过在保留符号顺序的同时插入非 lcs 符号，我们得到 scs：U[1..t]=abdcabdab。

很明显，r+t=m+n 用于两个输入序列。但是，对于三个或更多输入序列，这不成立。另请注意，lcs 和 scs 问题不是双重问题。

对于查找字符串的更一般问题，S 是一组字符串 S1,S2,...,Sl 的超字符串，问题是 NP-Complete。此外，对于普通情况可以找到良好的近似值，但对于最坏的情况则不然。

最短共同超序问题的例子：

https://i.stack.imgur.com/9i38E.jpg

时间复杂性： O(max(m,n))