2016/08/19 by Nakashima, Yuto, Inoue, Hiroe, Mieno, Takuya +3
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1608.05550
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 SUPSs 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 SUPSs for any subsequent query interval can be answered in O(k+1) time, where k is the number of outputs.