Search Results

The longest common subsequence (LCS) problem is a fundamental algorithmic problem. Given a pair of strings, the problem asks for the length of the longest string that is a subsequence in both input strings. Among the many relatives of this problem, there is its natural version where one or both of input strings have periodic structure. The case where only one of the input strings is periodic has been considered before; in this work, we develop an efficient algorithm for the more difficult case where both input strings are periodic. The algorithm is based on the existing algebraic framework for the LCS problem, developed by the third author; in particular, we extend this framework to dealing with affine (i.e. doubly-infinite periodic) permutations instead of finite ones. Given input strings that are a k-repeat of a period of length m and an 𝓁-repeat of a period of length n, the resulting algorithm runs in time O(mn+n log n log k), which is a substantial improvement over existing approaches. The algorithm has been implemented by the first author; by running his code, one can process pairs of periodic input strings with lengths far beyond the reach of all known alternative algorithms.