Algorithms for Longest Common Abelian Factors
Ali Alatabbi, Costas S. Iliopoulos, Alessio Langiu, M. Sohel Rahman · International Journal of Foundations of Computer Science · 2016
In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple [Formula: see text] time algorithm, where n is the length of the strings and [Formula: see text] is the alphabet size, and a sub-quadratic running time solution for the binary string case, both having linear space requirement. Furthermore, we present a modified algorithm applying some interesting tricks and experimentally show that the resulting algorithm runs faster.