后缀数组 后缀树 LCP

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