SuffixSort
后缀数组前置知识
后缀排序\((SuffixSort)\),是后缀数组的核心部分,但我不知道这玩意儿到底是怎么想出来的......(毕竟我不是神仙).然后,这个东西 并不是很难理解,我认为难的地方其实是在\(height_i\)的理解.所以....\(height\)我到现在也没理解.
先说一说后缀排序.
后缀排序是对后缀进行排序,这有啥用呢?如果没有\(height\),后缀数组就失去了它的魅力.但单纯的后缀排序也并非没有用.哎?不对,好像确实没啥用...但是这不影响我们学它.
后缀排序是对一个串的所有后缀进行排序,排序依据就是字典序.
一个显然的想法是把所有后缀都拿出来排一遍序,但显然这亚子太慢了,复杂度高达 \(O(nl \log_2{n})\) 最好也只能是 \(O(nl)\).因为字符串的比较是\(O(L)\)的.那么考虑怎样去优化这个排序.
我们可以发现,每次字符串的比较,如果我们知道这两个字符串相对应的两半的大小关系,那么我们可以直接得到这两个字符串的大小关系(类比线段的两个关键字的排序).这样是可以做到\(O(1)\)判断大小的.
那么我们这里就可以比较自然的想到使用倍增算法.我们先对所有的单个字符进行排序,这是\(O(n \log_2{n})\)的,这个复杂度可以接受,然后我们再对长度为\(2\)的串进行排序,以上一次排完序的单个字符大小关系为关键字.再对长度为\(4\)的串进行排序......以此类推.显然,最后我们一定能得到所有后缀的排序结果.
于是我们就倍增地枚举串的长度,进行排序,复杂度为\(O(n \log_2^2 {n})\).这样的复杂度已经足以应对不太刁钻的数据.
但是我们很可能仍然不满足于这样的复杂度.
我们注意到,对于字符串的排序,字符集一般不会太大,这也就告诉我们,基数排序或许是可行的.
事实上,多数情况下,都是可以使用基数排序的.
于是我们考虑基数排序,这其实就是桶排的强化版?或许就是桶排吧...
我们设桶数组是\(cnt\),那么\(pos\)对应的前缀和就是\(pos\)的排名.
要知道的是,基数排序是稳定排序.
于是我们把整个后缀排序的复杂度降至\(O(n \log_2{n})\).
\(sa[i]:\)第 \(i\) 小的后缀的编号.
\(rank[i]:\)编号为 \(i\) 的后缀的排名(从小到大).
于是总的代码长成这个亚子:
#include#include #include #include #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)#define per(i,a,b) for (int i = a ; i >= b ; -- i)const int N = 2e6 + 100 ;typedef int one[N] ;one trk , rk , SA , tmp , h , cnt ;int n , p ; char s[N] ;inline void SuffixSort () { p = 0 ; rep ( i , 1 , n ) p = std::max ( (int)s[i] , p ) ; rep ( i , 1 , n ) ++ cnt[s[i]] ; rep ( i , 1 , p ) cnt[i] += cnt[i-1] ; per ( i , n , 1 ) SA[cnt[s[i]]--] = i ; rk[SA[1]] = p = 1 ; rep ( i , 2 , n ) rk[SA[i]] = ( s[SA[i]] == s[SA[i-1]] ? p : ++ p ) ; for (int w = 1 ; w <= n ; w <<= 1) { MEM ( cnt , 0 ) ; rep ( i , 1 , n ) ++ cnt[rk[i+w]] ; rep ( i , 1 , p ) cnt[i] += cnt[i-1] ; per ( i , n , 1 ) tmp[cnt[rk[i+w]]--] = i ; MEM ( cnt , 0 ) ; rep ( i , 1 , n ) ++ cnt[rk[i]] ; rep ( i , 1 , p ) cnt[i] += cnt[i-1] ; per ( i , n , 1 ) SA[cnt[rk[tmp[i]]]--] = tmp[i] ; trk[SA[1]] = p = 1 ; rep ( i , 2 , n ) trk[SA[i]] = ( rk[SA[i]] == rk[SA[i-1]] && rk[SA[i]+w] == rk[SA[i-1]+w] ) ? p : ++ p ; rep ( i , 1 , n ) rk[i] = trk[i] ; }}
这一份代码是参考了 \(RXD\) 大爷的代码.
height数组
后缀数组的核心
\(height[i]:\)第 \(i\) 小的后缀和第 \(i-1\)小的后缀的最长公共前缀，
即 \(LCP(suffix[sa[i]],suffix[sa[i-1]])\)
任意两个后缀的最长公共前缀?设为后缀 \(x\) 和后缀 \(y\)，其中
\(rank[x] < rank[y]\)。答案就是
\[\min_{(rank[x],rank[y]]}{height[i]}\]
如果已经求出了\(height\),用\(ST\)表就可以\(O(n \: log_2 n)\)预处理，
\(O(1)\)回答两个后缀的最长公共前缀.
对于\(height\)数组:
有性质\(:height[rank[i]] ≥ height[rank[i-1]]-1\)
如果 \(height[rank[i-1]] = 0\) 显然成立，否则在 \(i-1\) 这个后
缀与它前驱的 \(LCP\) 的基础上去掉第一个字符，就找到了一个后
缀与 \(i\) 这个后缀的 \(LCP≥ height[rank[i-1]]-1\).
进而有 \(height[rank[i]] ≥ height[rank[i-1]]-1\)
于是按照原串的顺序求 \(height\) 就能做到线性了.
以上内容来自\(R\)爷.(我还是不太懂的...放在这里是为了以后方便复习.)
所以代码长这样:
for (int i = 1 , j = 0 ; i <= n ; ++ i) { if ( rk[i] == 1 ) continue ; while ( s[i+j] == s[SA[rk[i]-1]+j] ) ++ j ; h[rk[i]] = j ; if ( j ) -- j ;} 至于例题,\(UOJ\)和洛谷上都有大量板子题.