论文标题
计算最长（常见）林登子序列
Computing Longest (Common) Lyndon Subsequences
论文作者
论文摘要
给定一个带有长度$ n $的字符串$ t $，其字符是从大小$σ$的有序字母中绘制的，其最长的Lyndon子序列是$ t $的最长子序列，这是一个Lyndon Word。我们提出算法，以$ O（n^3）$（n）$ space或在$ o（n^3σ）$时空和时间在线查找$ O（n^3）$时间。我们可以使用$ O（n^3）$ space的两个长度$ n $ in $ o（n^4σ）$ time的长度$ n $ in $ o（n^4σ）$ time的长度$ n $的最长的林登子序列进行扩展。
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.
