String inference from longest-common-prefix array

DOI10.1016/J.TCS.2022.11.032MaRDI QIDQ2110373zbMATH OpenOpenAlexFDO

Authors Juha Kärkkäinen, Marcin Piatkowski, Simon J. Puglisi

Publication date 21 December 2022

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

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

zbMATH Keywords

BWTLCP arrayNP-hardnessstring inferencesuffix arraysuffix tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• String inference from longest-common-prefix array
• Permuted Longest-Common-Prefix Array
• Sampled Longest Common Prefix Array
• Mathematical Foundations of Computer Science 2003
• Inducing the LCP-array

Cites work

• Algorithms on Strings, Trees and Sequences
• An extension of the Burrows-Wheeler transform
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Border array on bounded alphabet
• Burrows-Wheeler transformations and de Bruijn words
• Computing longest previous factor in linear time and applications
• Counting permutations with given cycle structure and descent set
• Counting suffix arrays and strings
• Cover array string reconstruction
• Efficient validation and construction of border arrays and validation of string matching automata
• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• Inferring Strings from Lyndon Factorization
• Inferring strings from suffix trees and links on a binary alphabet
• Mathematical Foundations of Computer Science 2003
• On the combinatorics of suffix arrays
• Replacing suffix trees with enhanced suffix arrays
• Reverse engineering of compact suffix trees and links: a novel algorithm
• Reverse engineering prefix tables
• Reversing longest previous factor tables is hard
• Suffix Arrays: A New Method for On-Line String Searches
• Tighter bounds for the sum of irreducible LCP values
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Verifying and enumerating parameterized border arrays

Cited in

(5)

• Sampled Longest Common Prefix Array
• Permuted Longest-Common-Prefix Array
• Reconstructing parameterized strings from parameterized suffix and LCP arrays
• Reconstructing parameterized strings from parameterized suffix and LCP arrays
• Inverting parameterized Burrows-Wheeler transform

This page was built for publication: String inference from longest-common-prefix array

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