2021/05/25 by Mitsuru Funakoshi, Funakoshi, Mitsuru, Takuya Mieno +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #RNA and protein synthesis mechanisms
paper · pdf · doi:10.48550/arxiv.2105.11693
openalex publication_date 2021/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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σ+ (loglog n)2 + d) time where σ is the alphabet size. We also propose a variant of the algorithm, which runs in optimal O(1+d) time when the alphabet size is constant.