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]

[img]
Preview
Text
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:

Article

Identification Number (DOI):

https://doi.org/10.1016/j.tcs.2016.02.014

Keywords:

LZ-factorisation, Suffix automaton, Palindromes

Departments, Centres and Research Units:

Computing

Dates:

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

Item ID:

22723

Date Deposited:

09 Jan 2018 11:31

Last Modified:

29 Apr 2020 16:43

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

https://research.gold.ac.uk/id/eprint/22723

View statistics for this item...

Edit Record Edit Record (login required)