String Inference from Longest-Common-Prefix Array

DOI10.4230/LIPIcs.ICALP.2017.62zbMath1441.68302arXiv1606.04573OpenAlexW2742005078MaRDI QIDQ5111393

Simon J. Puglisi, Marcin Piątkowski, Juha Kärkkäinen

Publication date: 27 May 2020

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

zbMATH Keywords

NP-hardnesssuffix arraysuffix treeLCP arrayBWTstring inference

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Algorithms on strings (68W32)

Related Items (6)

Reverse-Safe Text Indexing ⋮ Inferring strings from position heaps in linear time ⋮ When a dollar makes a BWT ⋮ Tight upper and lower bounds on suffix tree breadth ⋮ On Suffix Tree Breadth ⋮ On the size of the smallest alphabet for Lyndon trees

This page was built for publication: String Inference from Longest-Common-Prefix Array