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 σ , 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 σ) time using O (n 2) space. [ABSTRACT FROM AUTHOR]