SPACE-ECONOMICAL SUFFIX TREE CONSTRUCTION ALGORITHM
SPACE-ECONOMICAL SUFFIX TREE CONSTRUCTION ALGORITHM
复制标题
DOI：
10.1145/321941.321946
复制
发表时间：
1976-01-01
影响因子：
2.5
通讯作者：
MCCREIGHT, EM
中科院分区：
文献类型：
--
作者：
MCCREIGHT, EM
提出了一种构造辅助数字搜索树的新算法，以辅助精确匹配子串搜索。该算法具有与已有算法相同的渐近运行时间界，但在空间上更经济。讨论了一些实现注意事项，并提出了在修改这些搜索树以响应它们索引的字符串的增量变化(更新问题)方面的新工作。
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.