4.3 Article

Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences

期刊

ALGORITHMICA
卷 -, 期 -, 页码 -

出版社

SPRINGER
DOI: 10.1007/s00453-023-01125-z

关键词

Lyndon word; Subsequence; Lexicographic order; Dynamic programming

向作者/读者索取更多资源

The article proposes two algorithms. One algorithm finds the longest Lyndon subsequence of a string T in O(n(3)) time complexity and O(n) space complexity, while the other algorithm finds the longest Lyndon subsequence online in O(n(3)) time complexity and space complexity. The first algorithm can also be extended to find the longest common Lyndon subsequence of two strings in O (n(4 )s) time complexity using O(n(2)) space complexity.
Given a string T of length n whose characters are drawn from an ordered alphabet of size s, its longest Lyndon subsequence is a maximum-length 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 at most n in O (n(4 )s) time using O(n(2)) space.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据