A note on the longest common Abelian factor problem

Abstract

Abelian string matching problems are becoming an object of considerable interest in last years. Very recently, Alatabbi et al. \cite{AILR2015} presented the first solution for the longest common Abelian factor problem for a pair of strings, reaching $O(\sigma n^2)$ time with $O(\sigma n\log n)$ bits of space, where $n$ is the length of the strings and $\sigma$ is the alphabet size. In this note we show how the time complexity can be preserved while the space is reduced by a factor of $\sigma$, and then how the time complexity can be improved, if the alphabet is not too small, when superlinear space is allowed.

v3 is vastly different to the previous one

References in corpus (1)

• Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time