Maximal anti-exponent of gapped palindromes

摘要

A palindrome is a string that reads the same backward as forward. We consider gapped palindromes which are words of the form uvũ for some words u, v with |v| ≥ 2 and where ũ denotes the reversal of u. Mimicking the standard notion of string exponent, we define the anti-exponent of a gapped palindrome uvũ as the quotient of |uvũ| over |uv|. We apply techniques based on the suffix automaton and the reversed Lempel-Ziv factorisation to an input string y containing no ordinary palindrome, and design an algorithm to compute the maximal anti-exponent of gapped palindromes occurring in the string. Our algorithm runs in linear-time on a fixed-size alphabet in contrast to a naive cubic time solution.