Shortest unique palindromic substring queries in optimal time

Abstract

A palindrome is a string that reads the same forward and backward. A palindromic substring $P$ of a string $S$ is called a shortest unique palindromic substring ($SUPS$) for an interval $[x,y]$ in $S$, if $P$ occurs exactly once in $S$, this occurrence of $P$ contains interval $[x,y]$, and every palindromic substring of $S$ which contains interval $[x,y]$ and is shorter than $P$ occurs at least twice in $S$. The $SUPS$ problem is, given a string $S$, to preprocess $S$ so that for any subsequent query interval $[x,y]$ all the $\mathit{SUPS}\mbox{s}$ for interval $[x,y]$ can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string $S$ of length $n$ in $O(n)$ time and space so that all $\mathit{SUPS}\mbox{s}$ for any subsequent query interval can be answered in $O(k+1)$ time, where $k$ is the number of outputs.

References in corpus (2)

• A Subquadratic Algorithm for Minimum Palindromic Factorization
• An In-place Framework for Exact and Approximate Shortest Unique Substring Queries