Longest (Sub-)Periodic Subsequence

Citations Over Time

Abstract

We present an algorithm computing the longest periodic subsequence of a string of length $n$ in $O(n^7)$ time with $O(n^4)$ words of space. We obtain improvements when restricting the exponents or extending the search allowing the reported subsequence to be subperiodic down to $O(n^3)$ time and $O(n^2)$ words of space.

Related Papers

• → On Two Variants of the Longest Increasing Subsequence Problem(2009)7 cited
• → The Longest Subsequence-Repeated Subsequence Problem(2023)4 cited
• → Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem(2010)3 cited
• → The Constrained Longest Common Subsequence Problem for Degenerate Strings(2007)4 cited
• → Longest (Sub-)Periodic Subsequence(2022)1 cited