Efficient Substring Traversal with Suffix Arrays
Toru Kasai, Hiroki Arimura, Setsuo Arikawa · QIR (Kyushu University Institutional Repository) (Kyushu University) · 2001
The substring traversal problem is the problem of enumerating all branching substrings appearing in a given text. Although this problem is easily solvable with the suffix tree of McCreight (1976), a space efficient and practically fast solution is important. We devise a simple and efficient algorithm that simulates the traversal of the suffix tree for a given text with the suJfix' arra!l of Manbet and Meyers (1993) and Gonnet, Baeza-Yates, Snider (1992) The algorithm runs in O(n) time and 5 bulk I/O with - the suffix array and an additional structure called the height arra!l, while the naive algorithm using binary search on the suffix array requires O(n 2) time in the worst case. The space requirement 7N bytes of our algorithm is smaller than 15N bytes of the traversal algorithm with the suffix tree. A linear time algerthru for computing the height array from the suffix and the height arrays is also presented. Computer experiments on real datasets showed that our traversal algorithm with the suffix array is an order of magnitude faster than the naive simulation method and comparable to the traversal algorithm with the suffix tree.