Efficient Computation of 2-Covers of a String.

DOI10.4230/LIPIcs.ESA.2020.77OpenAlexW3082037367MaRDI QIDQ5874549

Juliusz Straszyński, Jakub Radoszewski

Publication date: 7 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12943/pdf/LIPIcs-ESA-2020-77.pdf/

zbMATH Keywords

quasiperiodicity2-cover\(\lambda\)-covercover of a string

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

String covers of a tree, String Covering: A Survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing covers using prefix tables
• Enhanced string covering
• Fast algorithm for partial covers in words
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• The minimum substring cover problem
• An optimal algorithm for computing the repetitions in a word
• An on-line string superprimitivity test
• Testing string superprimitivity in parallel
• An optimal algorithm to compute all the covers of a string
• Two-dimensional prefix string matching and covering on square matrices
• Covering problems for partial words and for indeterminate strings
• Efficient algorithms for shortest partial seeds in words
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Covering a string
• Indexing weighted sequences: neat and efficient
• Approximate cover of strings
• An output-sensitive algorithm for the minimization of 2-dimensional string covers
• Computing the \(\lambda \)-covers of a string
• Two strings at Hamming distance 1 cannot be both quasiperiodic
• Can we recover the cover?
• An O(n log n) algorithm for finding all repetitions in a string
• Linear work suffix array construction
• Elementariness of a finite set of words is co-NP-complete
• Dynamic ordered sets with exponential search trees
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Deterministic sorting in O(nloglogn) time and linear space
• A Linear-Time Algorithm for Seeds Computation
• Quasi-Periodicity in Streams
• Solving the Minimum String Cover Problem
• Uniqueness Theorems for Periodic Functions
• The “Runs” Theorem
• Internal Pattern Matching Queries in a Text and Applications
• Algorithms on Strings
• Computing the cover array in linear time