Longest (Sub-)Periodic Subsequence
share
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.
READ FULL TEXT