In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple (σn2) time algorithm, where n is the length of the strings and σ 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.
|Number of pages||15|
|Journal||INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE|
|Publication status||Published - Aug 2016|