Finding top-\(k\) longest palindromes in substrings

DOI10.1016/j.tcs.2023.114183arXiv2210.02000MaRDI QIDQ6057835

Takuya Mieno, Kazuki Mitani, Kazuhisa Seto, Takashi Horiyama

Publication date: 26 October 2023

Published in: Theoretical Computer Science, WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

string algorithmspalindromestop-\(k\) queriesinternal queries

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• Computing minimal and maximal suffixes of a substring
• Counting distinct palindromes in a word in linear time
• Parallel detection of all palindromes in a string
• Semi-local string comparison: algorithmic techniques and applications
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• A substring-substring LCS data structure
• EERTREE: an efficient data structure for processing palindromes in strings
• Internal dictionary matching
• A data structure for substring-substring LCS length queries
• Dynamic and internal longest common substring
• Computing longest palindromic substring after single-character or block-wise edits
• Internal shortest absent word queries in constant time and linear space
• Time-space trade-offs for predecessor search
• Dynamic text and static pattern matching
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Online Sorted Range Reporting
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• A Linear Space Data Structure for Range LCP Queries*
• Repetition Detection in a Dynamic String
• Counting Palindromes in Substrings
• Optimal static range reporting in one dimension
• Almost optimal distance oracles for planar graphs
• Internal Pattern Matching Queries in a Text and Applications
• Minimal Suffix and Rotation of a Substring in Optimal Time
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Range LCP
• Episturmian words and some constructions of de Luca and Rauzy
• Compression by Contracting Straight-Line Programs