后缀树(英语:Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner于1973年提出,既而由McCreight在1976年和Ukkonen在1992年和1995年加以改进完善。
一个string S的后缀树是一个边(edge)被标记为字符串的树。因此每一个S的后缀都唯一对应一条从根节点到叶节点的路径。这样就形成了一个S的后缀的基数树(radix tree)。后缀树是前缀树(trie)里的一个特殊类型。
这是一篇与计算机相关的小作品。您可以通过编辑或修订扩充其内容。 |
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.