Average sizes of suffix trees and DAWGs

DOI10.1016/0166-218X(92)90270-KzbMath0679.68031OpenAlexW1971900185MaRDI QIDQ1822940

Anselm Blumer, David Haussler, Andrzej Ehrenfeucht

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90270-k

zbMATH Keywords

Mellin transformssuffix treestext retrievaldirected acyclic word graphsintegrals of meromorphic functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, Linear-size suffix tries, On Sturmian graphs, The palindromization map, Optimal insertion in deterministic DAWGs, On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns, \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity, WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING, Unnamed Item, Asymptotic estimation of the average number of terminal states in DAWGs, Reducing space for index implementation., On maximal repeats in strings

Cites Work

• The smallest automaton recognizing the subwords of a text
• Efficient On-Line Construction and Correction of Position Trees
• A Space-Economical Suffix Tree Construction Algorithm
• Unnamed Item
• Unnamed Item