A Generalization of the Linearized Suffix Tree to Square Matrices
Joong Chae Na, Sunho Lee, Dong Kyue Kim · Journal of Korea Multimedia Society · 2010
The linearized suffix tree (LST) is an array data structure supporting traversals on suffix trees. We apply this LST to two dimensional (2D) suffix trees and obtain a space-efficient substitution of 2D suffix trees. Given an n×n text matrix and an m×m pattern matrix over an alphabet Σ, our 2D-LST provides pattern matching in O(㎡log |Σ|) time and O(n²) space.