Optimal suffix tree construction with large alphabets

被引:283
作者
Farach, M [1 ]
机构
[1] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08855 USA
来源
38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年
关键词
D O I
10.1109/SFCS.1997.646102
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. Weiner [Wei73] who introduced the data structure, gave an O(n)-time algorithm far building the suffix: tree of an n-character string Brawn from a constant size alphabet. In the comparison model, there is a trivial Omega(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 fine for integer alphabet.
引用
收藏
页码:137 / 143
页数:7
相关论文
empty
未找到相关数据