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

Tools

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]

Preview

Text
GappedPalindromes01Feb.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.
Download (182kB) | Preview

Official URL: http://www.sciencedirect.com/science/article/pii/S...

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