前言

神仙们都会SA了,只剩我不会.

马上来补这个强大字符串算法.

什么是后缀数组

神 \(\mathrm{{\color{black}w}{\color{red}{ind\_whisper}}}\) 说 : 后缀数组就是对于字符串后缀建立的数组.

其实 \(\uparrow\) 这个定义还是比较贴切的 .

首先定义什么是后缀.

后缀就是一个字符串从某个位置开始,到该串末尾结束的子串.

定义 \(suf(x)\) 表示从 \(x\) 开始的子串.

如无特殊声明,本博客中 \(n\) 代表字符串长度.

后缀数组的主要由两个整数数组组成 :

\(sa_i\) 代表在字符串 \(s\) 所有后缀中排名为 \(i\) 的后缀的编号.

\(rk_i\) 代表 \(suf(i)\) 的排名.

构造后缀数组

从上述过程可知,我们要做的事情就是将字符串 \(s\) 的 \(n\) 个后缀排序.

然后考虑如何排序,直接对 \(n\) 个后缀做快速排序的话是 \(\mathcal{O} (n^2 \log n)\) 的.

这显然是太拉跨了,考虑更好的算法.

考虑类似倍增的过程 :

首先,对 \(s\) 的每个字符排序是很容易的,这其实就是对 \(s\) 的每一个长为 \(1\) 的子串排了序.

然后,如果我们有了对于每个长度为 \(w\) 的子串的排名 \(rnk_{w,1} \sim rnk_{w,n}\), 那么以 \(rnk_{w,i}\) 为第一关键字,\(rnk_{w,i + w}\) 为第二关键字排序就可以求出 \(rnk_{2w,1} \sim rnk_{2w,n}\) .

如果上述过程依然是快速排序实现的话,就得到了一个 \(\mathcal{O} (n \log^2 n)\) 的后缀排序了.

但是怎么可以因为排序算法而让倍增多一个 \(\log\) 呢.

可以发现整个排序过程中都是基于数值比较而不是特定规则比较进行的排序.

考虑使用 基数排序.

然后就得到了一份 \(\mathcal{O} (n \log n)\) 的后缀排序了.

模板 : \(\texttt{Link.}\)

Code :

巨大常数警告.

inline bool cmp(int x,int y,int w) {
    return mrk[x] == mrk[y] && mrk[x + w] == mrk[y + w];
}

void build_SA(int n) {
    int m = 256;
    ff(i,1,n) ++buc[rk[i] = s[i]];
    ff(i,1,m) buc[i] += buc[i - 1];
    fb(i,n,1) sa[buc[rk[i]]--] = i;
    
    for(int w = 1,p;;w <<= 1,m = p) {
        p = 0;
        for(int i = n;i > n - w;--i)
            id[++p] = i;
        ff(i,1,n) if(sa[i] > w)
            id[++p] = sa[i] - w;
        mems(buc,0);
        ff(i,1,n) ++buc[rad[i] = rk[id[i]]];
        ff(i,1,m) buc[i] += buc[i - 1];
        fb(i,n,1) sa[buc[rad[i]]--] = id[i];
        memcpy(mrk,rk,sizeof(rk));
        p = 0;
        ff(i,1,n)
            rk[sa[i]] = cmp(sa[i],sa[i - 1],w) ? p : ++p;
        if(p == n) {
            ff(i,1,n) sa[rk[i]] = i;
            break;
        }
    }
}

后缀为啥有用呢?子串本质上可以算作一个后缀的前缀，于是可以解决子串问题了。

SA 的 height 数组

定义 \(suf(i),suf(j)\) 的最长公共前缀(Longest Common Prefix) 长度为 \(lcp(i,j)\).

定义 \(height_i = lcp(sa_i,sa_{i - 1})\)

求 height :

inline void build_height(int n) {
    for(int i = 1,k = 0;i <= n;++i) {
        if(k) --k;
        while(s[i + k] == s[sa[rk[i] - 1] + k])
            ++k;
        h[rk[i]] = k;
    }
}

例题

T1

P4051 [JSOI2007]字符加密

首先破环成链,然后对链求 SA 即可实现把每个后缀排好序.

T2

P2870 [USACO07DEC]Best Cow Line G

从字符串首尾取字符加到新字符串的末尾,最小化字典序.

复杂度瓶颈在于比较原串和反串后缀大小.

那就把原串和反串连起来求 SA.

T3

P2408 不同子串个数

使用SAM

正难则反,求出相同的子串个数.

height是后缀的 LCP , 那么只需要统计后缀的相同前缀就得到了相同子串的个数了.

T4

P2852 [USACO06DEC]Milk Patterns G

求出现 \(k\) 次的子串的最长长度.

就是有连续 \(k\) 个后缀的 LCP 是这个子串.

求出每连续 \(k\) 个后缀的 LCP 的最小值,对于这些最小值取最大值即可.

求连续长度 \(k\) 区间最小值可以单调队列.