Inferring strings from suffix trees and links on a binary alphabet

DOI10.1016/j.dam.2013.02.033zbMath1329.68314OpenAlexW1971831237MaRDI QIDQ496548

Shunsuke Inenaga, Masayuki Takeda, Hideo Bannai, Tomohiro I.

Publication date: 22 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.033

zbMATH Keywords

enumeration problemsuffix treesreverse engineering problem

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (12)

Universal Reconstruction of a String ⋮ Inferring strings from Lyndon factorization ⋮ Recognizing union-find trees is NP-complete ⋮ Reverse engineering of compact suffix trees and links: a novel algorithm ⋮ Inferring strings from position heaps in linear time ⋮ Verifying and enumerating parameterized border arrays ⋮ When a dollar makes a BWT ⋮ Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info ⋮ Universal reconstruction of a string ⋮ On the size of the smallest alphabet for Lyndon trees ⋮ A suffix tree or not a suffix tree? ⋮ String inference from longest-common-prefix array

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting suffix arrays and strings
• Counting distinct strings
• On-line construction of suffix trees
• Validating the Knuth-Morris-Pratt Failure Function, Fast and Online
• Verifying a Parameterized Border Array in O(n 1.5) Time
• Cover Array String Reconstruction
• Counting Parameterized Border Arrays for a Binary Alphabet
• Efficient validation and construction of border arrays and validation of string matching automata
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Words over an ordered alphabet and suffix permutations
• REVERSE ENGINEERING PREFIX TABLES
• Mathematical Foundations of Computer Science 2003

This page was built for publication: Inferring strings from suffix trees and links on a binary alphabet