Data structures for computing unique palindromes in static and non-static strings

DOI10.1007/s00453-023-01170-8OpenAlexW4386284587MaRDI QIDQ6119834

Mitsuru Funakoshi, Takuya Mieno

Publication date: 25 March 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01170-8

zbMATH Keywords

string algorithmspalindromesdynamic data structuresrange minimum queriescompact data structuresshortest unique palindromic substrings

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Parallel detection of all palindromes in a string
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Preserving order in a forest in less than logarithmic time and linear space
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• On-line construction of suffix trees
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• Computing minimal unique substrings for a sliding window
• Minimal unique palindromic substrings after single-character substitution
• The heaviest induced ancestors problem: better data structures and applications
• Dynamic and internal longest common substring
• Computing longest palindromic substring after single-character or block-wise edits
• Palindromic trees for a sliding window and its applications
• Absent words in a sliding window with applications
• Tight tradeoffs for real-time approximation of longest palindromes in streams
• Shortest Unique Substrings Queries in Optimal Time
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Efficient algorithms for Lempel-Ziv encoding
• Repetition Detection in a Dynamic String
• Longest Lyndon Substring After Edit
• Longest Common Factor After One Edit Operation
• Path Minima Queries in Dynamic Weighted Trees
• Uniqueness Theorems for Periodic Functions

This page was built for publication: Data structures for computing unique palindromes in static and non-static strings