Longest Common Abelian Factors and Large Alphabets

Badkobeh, Golnaz; Gagie, Travis; Grabowski, Szymon; Nakashima, Yuto; Puglisi, Simon and Sugimoto, Shiho. 2016. Longest Common Abelian Factors and Large Alphabets. International Symposium on String Processing and Information Retrieval (SPIRE), pp. 254-259. [Article]

lcaf copy.pdf - Accepted Version
Available under License Creative Commons Attribution.

Download (231kB) | Preview

Abstract or Description

Two strings X and Y are considered Abelian equal if the letters of X can be permuted to obtain Y (and vice versa). Recently, Alatabbi et al. (2015) considered the longest common Abelian factor problem in which we are asked to find the length of the longest Abelian-equal factor present in a given pair of strings. They provided an algorithm that uses O(σn2) time and O(σn) space, where n is the length of the pair of strings and σ is the alphabet size. In this paper we describe an algorithm that uses O(n2log2nlog∗n) time and O(nlog2n) space, significantly improving Alatabbi et al.’s result unless the alphabet is small. Our algorithm makes use of techniques for maintaining a dynamic set of strings under split, join, and equality testing (Melhorn et al., Algorithmica 17(2), 1997).

Item Type:


Identification Number (DOI):



Suffix Tree, Extra Space, Alphabet Size, Factor Length, Alphabet Symbol

Related URLs:

Departments, Centres and Research Units:



26 June 2016Accepted
21 September 2016Published

Item ID:


Date Deposited:

17 May 2018 13:21

Last Modified:

29 Apr 2020 16:45

Peer Reviewed:

Yes, this version has been peer-reviewed.



View statistics for this item...

Edit Record Edit Record (login required)