Research Article
Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
https://doi.org/10.21203/rs.3.rs-2118135/v1
This work is licensed under a CC BY 4.0 License
published 06 May, 2023
You are reading this latest preprint version
Given a string T with length n whose characters are drawn from an ordered alphabet of size σ, 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) 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 σ) time using O(n 2) space.
Lyndon word
subsequence
lexicographic order
dynamic programming
No competing interests reported.
published 06 May, 2023
Editorial decision: Major revision
07 Feb, 2023
Reviews received at journal
29 Dec, 2022
Reviewers agreed at journal
19 Oct, 2022
Reviewers invited by journal
18 Oct, 2022
Editor assigned by journal
12 Oct, 2022
Submission checks completed at journal
01 Oct, 2022
First submitted to journal
29 Sep, 2022
You are reading this latest preprint version