A note on the longest common Abelian factor problem

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(σn^2)$ time with $O(σn \log n)$ bits of space, where $n$ is the length of the strings and $σ$ 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 $σ$, and then how the time complexity can be improved, if the alphabet is not too small, when superlinear space is allowed.

No reviews yet.

No comments yet.