Computing Longest (Common) Lyndon Subsequences

01/18/2022
by   Hideo Bannai, et al.
0

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^3) space.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset