## Abstract

The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. Weiner, who introduced the data structure, gave an O(n)-time algorithm for building the suffix tree of an n-character string drawn from a constant size alphabet. In the comparison model, there is a trivial Ω(n log n)-time lower bound based on sorting, and Weiner's algorithm matches this bound trivially. For integer alphabets, a substantial gap remains between the known upper and lower bounds, and closing this gap is the main open question in the construction of suffix trees. There is no super-linear lower bound, and the fastest known algorithm was the O(n log n) time comparison based algorithm. We settle this open problem by closing the gap: we build suffix trees in linear time for integer alphabet.

Original language | English (US) |
---|---|

Pages (from-to) | 137-143 |

Number of pages | 7 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - 1997 |

Event | Proceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA Duration: Oct 20 1997 → Oct 22 1997 |

## ASJC Scopus subject areas

- Hardware and Architecture