Name
Abstract | ||
|---|---|---|
A palindrome is a string that reads the same forward and backward. A palindromic substring $w$ of a string $T$ is called a minimal unique palindromic substring (MUPS) of $T$ if $w$ occurs only once in $T$ and any proper palindromic substring of $w$ occurs at least twice in $T$. MUPSs are utilized for answering the shortest unique palindromic substring problem, which is motivated by molecular biology [Inoue et al., 2018]. Given a string $T$ of length $n$, all MUPSs of $T$ can be computed in $O(n)$ time. In this paper, we study the problem of updating the set of MUPSs when a character in the input string $T$ is substituted by another character. We first analyze the number $d$ of changes of MUPSs when a character is substituted, and show that $d$ is in $O(\log n)$. Further, we present an algorithm that uses $O(n)$ time and space for preprocessing, and updates the set of MUPSs in $O(\log\sigma + (\log\log n)^2 + d)$ time where $\sigma$ is the alphabet size. We also propose a variant of the algorithm, which runs in optimal $O(d)$ time when the alphabet size is constant. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-86692-1_4 | SPIRE |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitsuru Funakoshi | 1 | 0 | 1.01 |
| Takuya Mieno | 2 | 4 | 3.48 |