Computing and Enumerating Minimal Common Supersequences Between Two Strings
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917359236677632 |
|---|---|
| author | Sopp, Braeden Liyanage, Adiesha Gong, Mingyang Zhu, Binhai |
| author_facet | Sopp, Braeden Liyanage, Adiesha Gong, Mingyang Zhu, Binhai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22591 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing and Enumerating Minimal Common Supersequences Between Two Strings Sopp, Braeden Liyanage, Adiesha Gong, Mingyang Zhu, Binhai Data Structures and Algorithms 68W01, 68W32, 68W40 F.2.2 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. |
| title | Computing and Enumerating Minimal Common Supersequences Between Two Strings |
| topic | Data Structures and Algorithms 68W01, 68W32, 68W40 F.2.2 |
| url | https://arxiv.org/abs/2603.22591 |