Linear-space LCS enumeration with quadratic-time delay for two strings
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913851795046400 |
|---|---|
| author | Sakai, Yoshifumi |
| author_facet | Sakai, Yoshifumi |
| contents | Suppose we want to seek the longest common subsequences (LCSs) of two strings as informative patterns that explain the relationship between the strings. The dynamic programming algorithm gives us a table from which all LCSs can be extracted by traceback. However, the need for quadratic space to hold this table can be an obstacle when dealing with long strings. A question that naturally arises in this situation would be whether it is possible to exhaustively search for all LCSs one by one in a time-efficient manner using only a space linear in the LCS length, where we treat read-only memory for storing the strings as excluded from the space consumed. As a part of the answer to this question, we propose an $O(L)$-space algorithm that outputs all distinct LCSs of the strings one by one each in $O(n^2)$ time, where the strings are both of length $n$ and $L$ is the LCS length of the strings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05742 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear-space LCS enumeration with quadratic-time delay for two strings Sakai, Yoshifumi Data Structures and Algorithms Suppose we want to seek the longest common subsequences (LCSs) of two strings as informative patterns that explain the relationship between the strings. The dynamic programming algorithm gives us a table from which all LCSs can be extracted by traceback. However, the need for quadratic space to hold this table can be an obstacle when dealing with long strings. A question that naturally arises in this situation would be whether it is possible to exhaustively search for all LCSs one by one in a time-efficient manner using only a space linear in the LCS length, where we treat read-only memory for storing the strings as excluded from the space consumed. As a part of the answer to this question, we propose an $O(L)$-space algorithm that outputs all distinct LCSs of the strings one by one each in $O(n^2)$ time, where the strings are both of length $n$ and $L$ is the LCS length of the strings. |
| title | Linear-space LCS enumeration with quadratic-time delay for two strings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.05742 |