On Abelian Longest Common Factor with and without RLE

Issue title: Foundations of Bioinformatics

Guest editors: Panagiotis Charalampopoulos, Maxime Crochemore and Solon P. Pissis

Article type: Research Article

Authors: Grabowski, Szymon^a | Kociumaka, Tomasz^b | Radoszewski, Jakub^{c; *}

Affiliations: [a] Institute of Applied Computer Science, Łódź University of Technology, Łódź, Poland. sgrabow@kis.p.lodz.pl | [b] Institute of Informatics, University of Warsaw, Warsaw, Poland. kociumaka@mimuw.edu.pl | [c] Institute of Informatics, University of Warsaw, Warsaw, Poland. jrad@mimuw.edu.pl

Correspondence: [*] Address for correspondence: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

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(n2/ log1+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 𝒪(m2σ2 log3m) time and 𝒪(m(σ2+log2m)) space, which employs line sweep, and one that works in 𝒪(m3) time and 𝒪(m) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known 𝒪(nm2)-time and 𝒪(m4)-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively.

Keywords: Abelian longest common factor problem, jumbled pattern matching, run-length encoding (RLE)

DOI: 10.3233/FI-2018-1740

Journal: Fundamenta Informaticae, vol. 163, no. 3, pp. 225-244, 2018