Longest

关于后缀数组的文件本文介绍后缀数组的基本概念、方法以及应用。首先介绍O(nlogn)复杂度构造后缀数组的倍增算法

关于后缀数组的文件本文介绍后缀数组的基本概念、方法以及应用。首先介绍O(nlogn)复杂度构造后缀数组的倍增算法，接着介绍了配合后缀数组的最长公共前缀 LCP（Longest Common Prefix）的计算方法，并给出一个线性时间内计算height 数组（记录跨度为1 的LCP 值的数组）的算法。为了让读者对如何运用后缀数组有一个感性认识，还介绍了两个应用后缀数组的例子：多模式串的模式匹配（给出每次匹配O(m+logn)时间复杂度的算法）以及求最长回文子串（给出O(nlogn)时间复杂度的算法）。最后对后缀数组和后缀树作了一番比较。

标签： nlogn 后缀数组基本概念复杂度

上传时间： 2013-12-21

上传用户：zhangliming420
Cognitive+Communication

The aim of this book, the first of two volumes, is to present selected research that has been undertaken under COST Action IC0902 ‘‘Cognitive Radio and Net- working for Cooperative Coexistence of Heterogeneous Wireless Networks’’ (http://newyork.ing.uniroma1.it/IC0902/). COST (European Cooperation in Sci- ence and Technology) is one of the Longest-running European frameworks sup- porting cooperation among scientists and researchers across Europe.

标签： Communication Cognitive

上传时间： 2020-05-26

上传用户：shancjb