经典算法系（3）-后缀数组&后缀树（Suffix Array & Suffix Tree）

经典算法系（3）-后缀数组&后缀树（Suffix Array & Suffix Tree）

3. 后缀数组(Suffix Array)

 后缀树和后缀数组都是处理字符串的有效工具，前者较为常见，但后者更容易编程实现，空间耗用更少；后缀数组可用于解决最长公共子串问题，多模式匹配问题，最长回文串问题，全文搜索等问题；

 后缀数组的基本元素：
 给定一个string，其长度为L，后缀指的是从string的某一个位置i（0<=i<L）开始到串末尾（string[L-1]）的一个子串，表示为suffix(i)；
 L个suffix(i)按照字典顺序排列并顺序存储在一个数组SA[L]中，则SA[L]称为后缀数组，其元素值存储的是suffix(i)的起始字符在string中的位置；
 每一个suffix[i]对应在SA[k]数组中的一个位置，将这个对应的位置存储为Rank[i]，时间复杂度为O(N)；对于任意两个suffix[i]和suffix[j]，由于知晓其在Rank[L]中的前后位置，所以在O(1)的时间内就可以得出他们的字典序大小关系；
 构建SA[i]数组中相邻元素的最长公共前缀（LCP，Longest Common Prefix），Height[i]表示SA[i]和SA[i-1]的LCP(i, j)；H[i]=Height[Rank[i］表示Suffix[i]和字典排序在它前一名的后缀子串的LCP大小；
对于正整数i和j而言，最长公共前缀的定义如下: LCP(i, j) =lcp(Suffix(SA[i]), Suffix(SA[j]))
                   =min(Height[k]|i+1<=k<=j)；
也就是计算LCP(i, j)等同于查找Height数组中下表在i+1到j之间的元素最小值
下述例子中如果LCP(0, 3)，则最小值为2，则"aadab"和"aabaaaab"的LCP为2

Read full article from 经典算法系（3）-后缀数组&后缀树（Suffix Array & Suffix Tree）