Efficient computation of maximal anti-exponent in palindrome-free strings

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 automaton and the reversed Lempel-Ziv factorisation. Our algorithm runs in O(n) time on a fixed-size alphabet or O(nlog⁡σ) on a large alphabet, which dramatically outperforms the naive cubic-time solution.