[后缀数组复习笔记]
首先推荐一篇写的非常好的Blog,本文中部分内容也会选自该博客。
个人认为后缀数组的核心内容其实就是对(2^x)的字符串按照(2^{x - 1})求出的第一第二关键字进行排序.然后进而一步一步对数组进行排序.
所以要用到基数排序：
基数排序在后缀数组中可以在(O(n))的时间内对一个二元组((p,q))进行排序，其中(p)是第一关键字，(q)是第二关键字
为了方便,本文用(i)代表(i)开头的后缀
首先我们要明确用到的数组的含义(非常重要！)
(sa_i):排名为(i)的后缀的位置
(rk_i):后缀(i)的排名
(x_i)后缀(i)的第一关键字
(y_i)基数排序的第二关键字,表示第二关键字为排名为(i)的后缀的位置
(c_i)(i)这个元素的出现次数,用于基数排序
(s),需要进行排序的字符串
利用倍增的思想。
因为上来当倍增长度为(1)时,没有第二关键字
第一关键字就是其字符大小.
倍增过程,(m)是其可以区分的后缀数量,(w)为当前的倍增长度.就是我上文说的(2^{x - 1})
这是后缀数组的核心之一.求出后缀(i)的第二关键字的大小
第一行：如果该后缀的长度不大于(2^{x - 1}),第二关键字对应的串就一定是空串.就没有排名一说了,直接顺序排下来.
第二行:如果当前为排名为(i)的后缀(此时的(sa_i)记录的长度还是(2^{x - 1 }),)他是(sa_i - w)的第二关键字,而我们是枚举的排名,所以(sa_i - w)这个后缀如果存在,他的第二关键字的排名一定是相应的排名.
基数排序不会就背吧QAQ(只需要理解第一第二关键字就好了)
基数排序完成后，(y)数组没用了,我们利用得到的(sa)求出新的(x_i)
但是(x_i)可能会重复,所以要利用上一轮的(x_i),这就是将(x)数组复制给(y)而不直接丢掉的原因.
如果(sa_i)和(sa_{i - 1})的第一关键字排名相同且向后倍增(2^{x - 1})也相同
那么(sa_i)和(sa_{i - 1})长度为(2^x)的后缀排名也是相同的.
height
上面得出的东西,都是为了(height)数组
我们引入一些概念
(lcp(x,y))：字符串(x)与字符串(y)的最长公共前缀，在这里(x)号后缀与(y)号后缀的最长公共前缀
(height[i])：(lcp(sa[i],sa[i−1]))，即排名为(i)的后缀与排名为(i−1)的后缀的最长公共前缀
(H[i])：(height[rak[i]])，第(i)号后缀与它前一名的后缀的最长公共前缀
那么有一个结论
(H[i] >= H[i - 1] - 1)
即
(height[rk[i]] >= height[rk[i - 1]] - 1)
利用这个性质,我们便可以(O(n))得出(height)
到这里后缀数组就完成了
但是关于(height)的应用是解大多数字符串题目的关键。掌握扎实
视题目而定,灵活应用