Computing and Enumerating Minimal Common Supersequences Between Two Strings
This addresses a specific computational problem in string algorithms, offering efficient solutions for minimal common supersequences, but it is incremental as it builds on known dynamic programming methods for the shortest case.
The paper tackles the problem of computing and enumerating minimal common supersequences for two input strings, achieving an O(n) time algorithm for computing one and an O(n) time delay for enumeration with O(n^2) space and O(n^3) construction time.
Given \(k\) strings each of length at most $n$, computing the shortest common supersequence of them is a well-known NP-hard problem (when \(k\) is unbounded). On the other hand, when \(k=2\), such a shortest common supersequence can be computed in \(O(n^2)\) time using dynamic programming as a textbook example. In this paper, we consider the problem of computing a \emph{minimal} common supersequence and enumerating all minimal common supersequences for \(k=2\) input strings. Our results are summarized as follows. A minimal common supersequence of \(k=2\) input strings can be computed in $O(n)$ time. (The method also works when \(k\) is a constant). All minimal common supersequences between two input strings can be enumerated with a data structure of $O(n^2)$ space and an $O(n)$ time delay, and the data structure can be constructed in $O(n^3)$ time.