Efficient Computation of Maximal Anti-Exponent in Palindrome-Free Strings

Badkobeh, Golnaz; Crochemore, Maxime; Mohamed, Manal and Toopsuwan, Chalita. 2016. Efficient Computation of Maximal Anti-Exponent in Palindrome-Free Strings. Theoretical Computer Science, 656(B), pp. 241-248. ISSN 0304-3975 [Article]

GappedPalindromes01Feb.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.

Download (182kB) | Preview

Abstract or Description

A palindrome is a string x = a1 · · · an which is equal to its reversal x = an · · · a1. We consider gapped palindromes which are strings of the form uvu , where u, v are strings, |v| ≥ 2, and u is the reversal of u. Replicating the standard notion of string exponent, we define the anti- exponent of a gapped palindrome uvu as the quotient of |uvu | by |uv|. To get an efficient computation of maximal anti-exponent of factors in a palindrome-free string, we apply techniques based on the suffix au- tomaton and the reversed Lempel-Ziv factorisation. Our algorithm runs in O(n) time on a fixed-size alphabet or O(n log σ) on a large alphabet, which dramatically outperforms the naive cubic-time solution.

Item Type:


Identification Number (DOI):



LZ-factorisation, Suffix automaton, Palindromes

Departments, Centres and Research Units:



12 February 2016Accepted
24 February 2016Published Online
20 December 2016Published

Item ID:


Date Deposited:

09 Jan 2018 11:31

Last Modified:

29 Apr 2020 16:43

Peer Reviewed:

Yes, this version has been peer-reviewed.



View statistics for this item...

Edit Record Edit Record (login required)