On Abelian Longest Common Factor with and without RLE

Abstract

We consider the Abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most n, and when the input strings are run-length encoded and their compressed representations have size at most m. The alphabet size is denoted by σ. For the uncompressed problem, we show an O(n²/ log^1+1/σn)-time and 𝒪(n)-space algorithm in the case of σ = 𝒪(1), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in 𝒪(m²σ² log³m) time and 𝒪(m(σ²+log²m)) space, which employs line sweep, and one that works in 𝒪(m³) time and 𝒪(m) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known 𝒪(nm²)-time and 𝒪(m⁴)-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively.