Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences

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.

Automated summary

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.