SA与SAM

SA 后缀数组

后缀排序顾名思义是对一个字符串的所有后缀进行按字典序排序的算法。排序的结果是一个 $sa$ 数组，其中 $sa_i=x$ 表示字符串排序后的字典序第 $i$ 小的后缀是 $S_{[x,n]}$ 这一个后缀。

考虑朴素算法，是将所有的后缀拉出来直接排序，复杂度 $O(n^2\log n)$。

后缀排序需要用到倍增的思想。首先求出每个长度为 $1$ 的子串的排名，即 $\{rk_1\}$。然后用该 $\{rk_1\}$ 作为下一次排序的第一与第二关键字，就可以求出每个长度为 $2$ 的子串的排名。依次类推，可以用 $\{rk_{2^w}\}$ 容易地推出 $\{rk_{2^{w+1}}\}$。当 $i+w>n$ 时，我们令 $rk_w[i]=-\infty$ 即可。这样倍增 $\log n$ 次就能求出后缀排序的结果。每次排序是 $O(n\log n)$ 的，因此复杂度 $O(n\log^2n)$。

我们又发现每次的排序是按两个关键字排序的，而值域又是 $[1,n]$ 故考虑采用基数排序，这样单次排序复杂度就是 $O(n)$ 的了，这样后缀排序的复杂度就优化到了 $O(n\log n)$。

但是这样写常数会很大（根据 OI Wiki），所有我们要进行一些常数优化，比如省略第二关键字的排序，同时优化基数排序的值域，带 rk 全部不同时直接退出倍增等。具体细节可以见代码。

SA 求 height 数组

height 数组定义为 $\text{LCP}(sa_i,sa_{i-1})$。特别地，$height_1=0$。

height 有一个性质：$height_{rk_i}\ge height_{rk_{i-1}}-1$。因此 height 数组就可以 $O(n)$ 求解了。证明见 OI wiki。

SA 模板代码

bool cmp(int x,int y,int len){
  return oldrk[x]==oldrk[y]&&oldrk[x+len]==oldrk[y+len];
}
void getsa(){
  rep(i,1,n) cnt[rk[i]=s[i]]++;
  rep(i,1,m) cnt[i]+=cnt[i-1];
  per(i,n,1) sa[cnt[rk[i]]--]=i;
  for(int len=1;;len<<=1,m=p){
    p=0; per(i,n,n-len+1) id[++p]=i;
    rep(i,1,n) if(sa[i]>len) id[++p]=sa[i]-len;
    memset(cnt,0,(m+1)*sizeof(int));
    rep(i,1,n) cnt[key[i]=rk[id[i]]]++;
    rep(i,1,m) cnt[i]+=cnt[i-1];
    per(i,n,1) sa[cnt[key[i]]--]=id[i];
    memcpy(oldrk+1,rk+1,n*sizeof(int));
    p=0; rep(i,1,n) rk[sa[i]]=cmp(sa[i],sa[i-1],len)?p:++p;
    if(p==n){
      rep(i,1,n) sa[rk[i]]=i;
      break;
    }
  }
}
void getheight(){
  rep(i,1,n) rk[sa[i]]=i;
  int tmp=0;
  rep(i,1,n){
    if(rk[i]==1) continue;
    if(tmp>0) tmp--;
    int j=sa[rk[i]-1];
    while(j+tmp<=n&&i+tmp<=n&&s[i+tmp]==s[j+tmp]) tmp++;
    height[rk[i]]=tmp;
  }
}

其中 $s$ 为要求解的字符串，$n$ 是字符串长度，$m$ 是字典大小。

SA 与 height 的应用

先写一些，见到了再积累。

求两个位置开始的串的 LCP

众所周知，$\text{LCP}(sa_i,sa_{j})=\min\limits_{k=i+1}^j\{height_k\}$，所以直接对 height 建 ST 表，求 LCP 就变成了区间最小值问题。

求字符串本质不同子串个数

先算所有子串的个数，再减去重复的。所以就是 $\frac{n(n-1)}{2}-\sum{height_i}$。