Longest Palindromic Substring in Sublinear Time

We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated (n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, (n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0,σ) can be stored in (n log σ/log n) space and read in (n log σ/log n) time. We devise a simple (n log σ/log n)-time algorithm for computing a longest palindromic substring. In particular, our algorithm works in sublinear time if σ = 2^{o(log n)}. Our technique relies on periodicity and on the (n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in (1) time.