随笔 - 6, 文章 - 0, 评论 - 24, 引用 - 0
数据加载中……

Suffix Tree—后缀树

Suffix tree—后缀树

l  简介

后缀树是一种PAT树,它描述了给定字符串的所有后缀,许多重要的字符串操作都能够在后缀树上快速地实现。

l  定义

一个长度为n的字符串S,它的后缀树定义为一棵满足如下条件的树:

n  从根到树叶的路径与S的后缀一一对应。即每条路径惟一代表了S的一个后缀;

n  每条边都代表一个非空的字符串;

n  所有内部节点(根节点除外)都有至少两个子节点。

由于并非所有的字符串都存在这样的树,因此S通常使用一个终止符号进行填充(通常使用$)。

l  优点

n  匹配快。对于长度为m的模式串,只需花费至多O(m)的时间进行匹配。

n  空间省。Suffix tree的空间耗费要低于Suffix trie,因为Suffix tree除根节点外不允许其内部节点只含单个子节点,因此它是Suffix trie的压缩表示。





待续……

posted on 2009-03-29 13:05 yuyang7 阅读(12088) 评论(8)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: Suffix Tree—后缀树  回复  更多评论   

学习~~
简介中第一句“所有前缀”是不是应该是“所有后缀”?
另外,请教博主,你的图画得很漂亮,不知道是用什么工具画的?
2009-03-29 14:11 | t

# re: Suffix Tree—后缀树  回复  更多评论   

@t
笔误,已更正。
图其实是用PowerPoint画的。
2009-03-29 14:22 | yuyang7

# re: Suffix Tree—后缀树  回复  更多评论   

@yuyang7
PowerPoint?强!
2009-03-29 16:55 | t

# re: Suffix Tree—后缀树[未登录]  回复  更多评论   

应该再详细些阿 。。。。
2009-06-22 21:43 | Simon

# re: Suffix Tree—后缀树  回复  更多评论   

不错,说得很清楚。
2010-08-08 21:36 | 游客

# re: Suffix Tree—后缀树  回复  更多评论   

准备实做下
2011-01-28 23:42 | 神奇哥

# re: Suffix Tree—后缀树  回复  更多评论   

不错,顶下
2011-05-24 16:01 |

# re: Suffix Tree—后缀树  回复  更多评论   

8错
2011-09-22 09:51 | 程序员面试之家

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理