Computing string covers in sublinear time

DOI10.1007/S00224-025-10258-3MaRDI QIDQ7233452zbMATH OpenFDO

Authors Jakub Radoszewski, Wiktor Zuba

Publication date 27 April 2026

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

Full work available at URL https://doi.org/10.1007/S00224-025-10258-3

zbMATH Keywords

covercover arrayquasiperiodpacked string matchingpillar model

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 6850408 (Why is no real title available?)
• scientific article; zbMATH DE number 7651115 (Why is no real title available?)
• scientific article; zbMATH DE number 7740885 (Why is no real title available?)
• scientific article; zbMATH DE number 7695994 (Why is no real title available?)
• A linear-time algorithm for seeds computation
• An on-line string superprimitivity test
• Balancing Straight-line Programs
• Cover array string reconstruction
• Detecting regularities on grammar-compressed strings
• Dynamic suffix array with polylogarithmic queries and updates
• Enhanced string covering
• Fast Pattern Matching in Strings
• Faster approximate pattern matching: a unified approach
• Finding all periods and initial palindromes of a string in parallel
• Internal Quasiperiod Queries
• Internal pattern matching queries in a text and applications
• Linear time construction of cover suffix tree and applications
• Longest palindromic substring in sublinear time
• Lyndon Words, the Three Squares Lemma, and Primitive Squares
• Lyndon arrays in sublinear time
• Optimal superprimitivity testing for strings
• Quantum speed-ups for string synchronizing sets, longest common substring, and \(k\)-mismatch matching
• Quasiperiodicities in Fibonacci strings.
• Shortest cover after edit
• Shortest covers of all cyclic shifts of a string
• Squares, cubes, and time-space efficient string searching
• String matching in O( n+ m) quantum time
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• The maximum number of squares in a tree
• Towards optimal packed string matching
• Uniqueness Theorems for Periodic Functions

This page was built for publication: Computing string covers in sublinear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7233452)