- 博客(0)
- 资源 (3)
空空如也
suffix tree—后缀树的典型应用
Suffix trees have numerous applications, often providing
linear-time solutions to challenging string problems
A selection of them:
Exact matching
Common substrings, with applications
Matching statistics
Suffix arrays
Genome-scale projects
2008-11-27
后缀数组的一种实现方法
在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树
大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后
缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的
很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。
可以说,在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想
介绍一下后缀数组的基本概念、构造方法,以及配合后缀数组的最长公共前缀
数组的构造方法,最后结合一些例子谈谈后缀数组的应用。
2008-11-27
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人