Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings

DOI10.1007/s00224-020-09980-xzbMath1503.68317arXiv1903.06290OpenAlexW3021816736MaRDI QIDQ2032287

Masayuki Takeda, Hideo Bannai, Shunsuke Inenaga, Kiichi Watanabe, Yuto Nakashima

Publication date: 11 June 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.06290

zbMATH Keywords

run-length encodingstring algorithmspalindromesshortest unique substrings

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Algorithms on strings (68W32)

Related Items

Minimal unique palindromic substrings after single-character substitution, Shortest unique palindromic substring queries in semi-dynamic settings, Data structures for computing unique palindromes in static and non-static strings, Palindromic trees for a sliding window and its applications

Uses Software

• EERTREE

Cites Work

• Unnamed Item
• Parallel detection of all palindromes in a string
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• EERTREE: an efficient data structure for processing palindromes in strings
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Optimal bounds for the predecessor problem and related problems
• Shortest unique palindromic substring queries on run-length encoded strings
• In-place algorithms for exact and approximate shortest unique substring problems
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Shortest Unique Substrings Queries in Optimal Time
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Shortest Unique Substring Query Revisited
• Episturmian words and some constructions of de Luca and Rauzy