后缀数组
以前学了，虽然写了板子，但是好像没学懂，所以重学一遍，随便做了几道板题。
定义
\(sa_i\) :排名第 \(i\) 的后缀是哪一个。
\(rk_i\):第 \(i\) 个后缀的排名。
做法
主要是倍增，每一个后缀初始长度为 \(1\)，然后倍增长度扩展，维护每一轮的排序结果。
让一个长度为 \(2^i\) 的串被长度为两个 \(2^{i-1}\) 的串拼出来。
若长度不足，则后面的串就当是 \(0\)，然后拼起来之后的排序就是相当于对两个串 \(2^{i-1}\) 进行一个双关键字排序。
可以直接用 \(rk\) 数组代表两个串，设长度为 \(k\)，就是对二元组 \((rk_{sa_i},rk_{sa_i+k})\) 进行排序。
直接用 \(sort\) 可以做到 \(O(nlog^2n)\)。
int cmp(int x,int y)
{
if(rk[x] != rk[y]) return rk[x] < rk[y] ;
int i = x+p>n?0:x+p ;
int j = y+p>n?0:y+p ;
return rk[i] < rk[j] ;
}
void Init()
{
FOR(i,1,n,1) sa[i] = i,rk[i] = a[i] ;
FOR(j,1,n,j)
{
p = j,sort(sa+1,sa+1+n,cmp) ;
FOR(i,1,n,1) tmp[sa[i]] = tmp[sa[i-1]]+cmp(sa[i-1],sa[i]) ;
FOR(i,1,n,1) rk[i] = tmp[i] ;
}
}
然后 \(sort\) 可以用基数排序优化掉。
简单地说就是先对第二关键字进行计数排序，然后再对第一关键字进行计数排序。
然后用 \(vector\) 常数很大，你只要记一个长度，然后就可以压到一个数组里面了。
int m = N-3 ;
FOR(i,1,n,1) sa[i] = i,rk[i] = s[i] ;
FOR(k,1,n,k)
{
me(cnt,0) ; int top = 0 ;
FOR(i,1,n,1) ++cnt[rk[sa[i]+k]] ;
FOR(i,1,m,1) cnt[i] += cnt[i-1] ;
ROF(i,n,1,1) tmp[cnt[rk[sa[i]+k]]--] = sa[i] ;
me(cnt,0) ;
FOR(i,1,n,1) ++cnt[rk[tmp[i]]] ;
FOR(i,1,m,1) cnt[i] += cnt[i-1] ;
ROF(i,n,1,1) sa[cnt[rk[tmp[i]]]--] = tmp[i] ;
FOR(i,1,n,1) top += make_pair(rk[sa[i-1]],rk[sa[i-1]+k])!=make_pair(rk[sa[i]],rk[sa[i]+k]),tmp[sa[i]] = top ;
FOR(i,1,n,1) rk[i] = tmp[i] ;
}
Hight
\(Hight_i\) :表示的是 \(sa_i\) 和 \(sa_{i-1}\) 的 \(LCP\)。
这东西可以和区间 \(min\) 结合起来，很好用，证不会证，但是很好背。
int k = 0 ;
FOR(i,1,n,1)
{
if(k) --k ; int j = sa[rk[i]-1] ;
while(s[i+k] == s[j+k]) ++k ; hi[rk[i]] = k ;
}
T
P4051 [JSOI2007] 字符加密
Sol
比较简单的题，显然就是对所有的环形字符串进行后缀排序。
将字符串复制一遍，然后就是求跨过的子串的排序。
容易发现全部加上一段后缀不影响，所以直接后缀排序，然后扫 \(sa\) 数组就行了。
P2852 [USACO06DEC] Milk Patterns G
Sol
这道题要用到 \(Hight\) 数组。
由于是后缀的 \(Lcp\)，显然这些 \(Lcp\) 是没有完全重合的，也就是说不会算重。
算出 \(Hight\) 数组之后，求出所有长度为 \(k-1\) 的区间的 \(Hight\) 最小值的最大值就好了。
P4248 [AHOI2013] 差异
Sol
题目已经给得很裸了。
显然前面那一坨加的是定值，我们只需要求后面那一坨就好了。
两个后缀的 \(Lcp\) 是他们 \(sa\) 之间的 \(Hight\) 的最小值。
所以对每一个 \(Hight\) 求出是最小值的区间就好了。
值得注意的是，单调栈左边取等，右边不取等，这样就不会算重。