最短的常見超序問題基本資訊

在最短的通用超級序列是密切相關的最長公共子，你可以作為承擔這一任務的外部功能使用上有問題。最短的共同超級序列問題是與最長公共子序列問題密切相關的問題。

最短的常見超序（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))