SA

401rk8 · 2021-06-23 22:03:37 · 个人记录

前置知识：倍增、计数排序
应用部分：多种数据结构

构建

概述

后缀数组（Suffix Array）旨在预处理后缀的排名数组来处理字符串问题，算法本身重在构建 SA 数组，应用可以与多种数据结构结合。

构建算法有倍增（O(n\log n)）、DC3（O(n)，常数大）、SA-IS（O(n)）等，本文只介绍倍增。

【模板】后缀排序

记号

• s$ 为字符串，其长度 $|s|=n
• 后缀 suf(i)=s[i..n]
• 字符串间的大小按字典序比较，空字符认为为 -\inf
• 数组 sa[i] 表示 s 的后缀中第 i 小的是 sa[i]；rk[i] 表示 suf(i) 为第 rk[i] 小。显然 sa 与 rk 互逆，即 sa[rk[i]]=rk[sa[i]]=i

倍增

每次对长度为 2^i 的子串后缀排序，而这个后缀可以用两个 2^{i-1} 的拼成。
由于长度为 2^{i-1} 的已排过序，因此排 2^i 的时只需用上一次的 rk 进行双关键字计数排序。

常数优化

• 第二关键字无需计数排序：利用上一次的 sa
• 优化计数排序：新值域为每次排完后不同 rk 的个数
• 减少不连续内存访问
• 若 rk 都不相同则直接生成 sa

过程

• 对长度为 1 的子串计数排序

m = 130; // m根据字符集设 
For(i,1,n) ++cnt[ rk[i]=s[i] ];
For(i,1,m) cnt[i] += cnt[i-1];
rFor(i,n,1) sa[ cnt[rk[i]]-- ] = i;

• 倍增

bool cmp(int i,int j,int w) { return rk0[i]==rk0[j] && rk0[i+w]==rk0[j+w]; }
// 多测记得mem(rk0)，因为要用到rk0[i+w]
for(int w = 1, p = 0; p < n; w *= 2, m = p) {
    // w为长度；p=n时rk都不同，结束；m=p优化值域
    p = 0;
    // 第二关键字：
    For(i,n-w+1,n) id[++p] = i; // 第二关键字为0
    For(i,1,n) if( sa[i] > w ) id[++p] = sa[i]-w; // sa[i]作为sa[i]-w的第二关键字 
    // id[i]为按第二关键字排序后第i小的后缀；
    // 第一关键字：相当于把i换成id[i]
    mem(cnt,0,m);
    For(i,1,n) ++cnt[ h[i]=rk[id[i]] ]; // 存下来rk[id[i]]优化内存访问
    For(i,1,m) cnt[i] += cnt[i-1];
    rFor(i,n,1) sa[ cnt[h[i]]-- ] = id[i];
    p = 0, memcpy(rk0+1,rk+1,sizeof(int)*n); // rk0用于比对两个子串是否相等（板子中为h）
    For(i,1,n) rk[sa[i]] = cmp(sa[i-1],sa[i],w) ? p : ++p;
    // cmp优化内存访问；相等子串的rk也要相同
}

height

定义