Name
Abstract | ||
|---|---|---|
Given a string $T$ with length $n$ whose characters are drawn from an ordered alphabet of size $\sigma$, its longest Lyndon subsequence is a longest subsequence of $T$ that is a Lyndon word. We propose algorithms for finding such a subsequence in $O(n^3)$ time with $O(n)$ space, or online in $O(n^3 \sigma)$ space and time. Our first result can be extended to find the longest common Lyndon subsequence of two strings of length $n$ in $O(n^4 \sigma)$ time using $O(n^3)$ space. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/978-3-031-06678-8_10 | International Workshop on Combinatorial Algorithms (IWOCA) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hideo Bannai | 1 | 620 | 79.87 |
| Tomohiro I | 2 | 148 | 22.06 |
| Tomasz Kociumaka | 3 | 0 | 1.35 |
| Dominik Köppl | 4 | 30 | 10.31 |
| Simon J. Puglisi | 5 | 0 | 2.37 |