TY - GEN
T1 - Shortest unique palindromic substring queries in optimal time
AU - Nakashima, Yuto
AU - Inoue, Hiroe
AU - Mieno, Takuya
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - 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 [s, t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s, t], and every palindromic substring of S which contains interval [s, t] 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 [s, t] all the SUPSs for interval [s, t] 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(α + 1) time, where α is the number of outputs.
AB - 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 [s, t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s, t], and every palindromic substring of S which contains interval [s, t] 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 [s, t] all the SUPSs for interval [s, t] 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(α + 1) time, where α is the number of outputs.
UR - https://www.scopus.com/pages/publications/85045984814
UR - https://www.scopus.com/pages/publications/85045984814#tab=citedBy
U2 - 10.1007/978-3-319-78825-8_32
DO - 10.1007/978-3-319-78825-8_32
M3 - Conference contribution
AN - SCOPUS:85045984814
SN - 9783319788241
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 397
EP - 408
BT - Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers
A2 - Smyth, William F.
A2 - Brankovic, Ljiljana
A2 - Ryan, Joe
PB - Springer Verlag
T2 - 28th International Workshop on Combinational Algorithms, IWOCA 2017
Y2 - 17 July 2017 through 21 July 2017
ER -