Universal reconstruction of a string

DOI10.1016/j.tcs.2019.10.027zbMath1435.68398OpenAlexW2980927988WikidataQ127013082 ScholiaQ127013082MaRDI QIDQ2297860

Jakub Radoszewski, Wojciech Rytter, Tomasz Kociumaka, Tomasz Walen, Paweł Gawrychowski

Publication date: 20 February 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.10.027

zbMATH Keywords

minimal spanning treerun in a stringmaximal palindromesstring recovery

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (4)

String covers of a tree ⋮ String Covering: A Survey ⋮ Sequence graphs realizations and ambiguity in language models ⋮ Experimental evaluation of algorithms for computing quasiperiods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reverse engineering of compact suffix trees and links: a novel algorithm
• Indeterminate strings, prefix arrays \& undirected graphs
• Inferring strings from suffix trees and links on a binary alphabet
• Verifying and enumerating parameterized border arrays
• An on-line string superprimitivity test
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets
• Inferring an indeterminate string from a prefix graph
• A suffix tree or not a suffix tree?
• New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
• Inferring strings from Lyndon factorization
• INFERRING STRINGS FROM COVER ARRAYS
• Universal Reconstruction of a String
• Linear work suffix array construction
• Inferring Strings from Full Abelian Periods
• Verifying a Parameterized Border Array in O(n 1.5) Time
• Cover Array String Reconstruction
• Efficient validation and construction of border arrays and validation of string matching automata
• Jewels of Stringology
• Reversing Longest Previous Factor Tables is Hard
• The “Runs” Theorem
• REVERSE ENGINEERING PREFIX TABLES
• Mathematical Foundations of Computer Science 2003
• Algorithms on Strings
• Computing the cover array in linear time
• Recovering, counting and enumerating strings from forward and backward suffix arrays

This page was built for publication: Universal reconstruction of a string