A Generalization of the Suffix Tree to Square Matrices, with Applications

DOI10.1137/S0097539792231982zbMath0834.68038OpenAlexW1963953096MaRDI QIDQ4842120

Raffaele Giancarlo

Publication date: 18 March 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792231982

zbMATH Keywords

Lsuffix treetwo-dimensional dictionary matchingtwo-dimensional pattern retrieval

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Data structures (68P05) Computing methodologies for text processing; mathematical typography (68U15)

Related Items

Dynamic suffix tree and two-dimensional texts management ⋮ On updating suffix tree labels ⋮ TREE-BASED 2D INDEXING ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Linear-time construction of two-dimensional suffix trees ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Finding maximal 2-dimensional palindromes ⋮ 2D Lyndon words and applications ⋮ On-line construction of two-dimensional suffix trees ⋮ \(LZ\)-based image compression ⋮ Unnamed Item ⋮ Improving on-line construction of two-dimensional suffix trees for square matrices ⋮ A Note on a Tree-Based 2D Indexing ⋮ Cartesian Tree Matching and Indexing ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Sequential and indexed two-dimensional combinatorial template matching allowing rotations