后缀数组

定义 sa[i] 表示排名为 $i$ 的后缀的位置，rk[i] 为后缀 $i$ 的排名。

倍增求，每轮通过已有信息 $sa_w,rk_w$ 来推出 $sa_{2w},rk_{2w}$，其中 $sa_w$ 表示仅考虑 $[i,\min\{i+w-1,n\}]$ 时的信息。推的过程即把 $(rk_w[i],rk_w[i+w])$ 双关键字排序，这一步使用基数排序即可做到线性，总复杂度 $O(n\log n)$。

代码细节部分，定义 se[i] 表示第二关键字排名为 $i$ 的后缀的位置，t 是一个临时的桶数组。

对于每一轮 $w\to 2w$ 的过程，我们先把 se[i] 维护好：

int x=0;
For(i,1,w)se[++x]=n-w+i;
For(i,1,n)if(sa[i]>w)se[++x]=sa[i]-w;

即先把 $i+w>n$ 的位置放入，再根据 sa 依次枚举排名从大到小的 $i+w$ 放入。

然后就维护好了这轮的 se 就可以配合 rk 进行一轮基数排序来更新 sa 了，定义 $[1,m]$ 为当前 $rk$ 的值域：

For(i,1,m)t[i]=0;
For(i,1,n)t[rk[i]]++;
For(i,2,m)t[i]+=t[i-1];
Rof(i,n,1)sa[t[rk[se[i]]]--]=se[i];

即给每个 $rk_i$ 的值分配了连续的一段排名，于是让第二关键字排名更大的先领取对应段里的大排名。

得到了新的 sa 之后还需要更新 rk，代码实现上借用当前无用的 se 数组来存储以前的 rk 信息：

memcpy(se,rk,sizeof rk);
rk[sa[1]]=p=1;For(i,2,n)
    rk[sa[i]]=(se[sa[i-1]]==se[sa[i]]&&se[sa[i-1]+w]==se[sa[i]+w])?p:++p;
m=p;

注意此时访问 sa[i]+w 可能会恰好溢出到 $n+1$ 位置。

只需要 $m=n$ 就可以停止倍增过程。初始化时因为要执行一次基数排序，注意让 se[i]=i。

const int N=1e6+10;
int n;char s[N];
int sa[N],se[N],rk[N],m,t[N];
void qsort(){
    For(i,1,m)t[i]=0;
    For(i,1,n)t[rk[i]]++;
    For(i,2,m)t[i]+=t[i-1];
    Rof(i,n,1)sa[t[rk[se[i]]]--]=se[i];
}
signed main(){
    scanf("%s",s+1),n=strlen(s+1),m=100;
    For(i,1,n)rk[i]=s[i]-'0'+1,se[i]=i;qsort();
    for(int w=1;;w<<=1){
        int p=0;For(i,1,w)se[++p]=n-w+i;
        For(i,1,n)if(sa[i]>w)se[++p]=sa[i]-w;
        qsort(),memcpy(se,rk,sizeof rk);
        rk[sa[1]]=p=1;For(i,2,n)
            rk[sa[i]]=(se[sa[i]]==se[sa[i-1]]&&se[sa[i]+w]==se[sa[i-1]+w])?p:++p;
        m=p;if(m==n)break;
    }For(i,1,n)printf("%d ",sa[i]);
    return 0;
}

需要注意的是，在更新 $rk$ 时的 sa[i]+w 会至多溢出到 $n+1$ 的位置。

P2870，给定串 $S_{1\cdots n}$，初始有空串 $T$，每次可以把 $S$ 的首字符或尾字符挪入 $T$ 的末尾，求最小的 $T$ 的字典序。$1\leq n\leq 5\times 10^5$。

考虑一种贪心，放左右字符字典序更小的，如果遇到相等的则需要判断 $l$ 开始的后缀与 $r$ 开始的前缀的字典序，这一步可以通过对在末尾添加了翻转后的 $S$ 的串做后缀排序，比较后缀 $l$ 与后缀 $n+(n-r+1)$（前缀 $r$）的排名。$O(n\log n)$。

height 数组

定义 $\operatorname{lcp}(i,j)$ 为后缀 $i,j$ 的 lcp，则 $height_i=\text{lcp}(sa_i,sa_{i-1})$。存在线性求 $height$ 数组的做法，基于以下性质：

$height_{rk_i}\ge height_{rk_{i-1}}-1$。

证明：记 $h_i=height_{rk_i}$，需要证明的就是 $h_i\ge h_{i-1}-1$。有 $h_i=\text{lcp}(i,sa_{rk_i-1})$，即后缀 $i$ 与排名在 $i$ 前一名的后缀的 $\text{lcp}$。

设后缀 $k=sa_{rk_{i-1}-1}$，即排名在后缀 $i-1$ 前一名的后缀，则：

• 若 $h_{i-1}\leq 1$，显然成立；
• 若 $h_{i-1}>1$，设后缀 $i-1$ 为 $aAB$（小写表示单字符，大写表示一个串），后缀 $i$ 则为 $AB$。设后缀 $k$ 为 $aAD$，则 $h_{i-1}=|A|+1$ 且 $D<B$。发现 $\text{lcp}(i,k+1)\ge |A|=h_{i-1}-1$，并且由于 $A=A,D<B$，$k+1$ 的排名一定在 $i$ 之前，则排名在 $[rk_{k+1},rk_i]$ 之间的后缀都至少有 $A$ 这个前缀，那么 $h_i\ge |A|=h_{i-1}-1$，得证。

于是我们得到了一种线性求 $height$ 数组的做法：按照 $h_{1\to n}$ 的顺序求，每次初始 $h_i=\max\{h_{i-1}-1,0\}$ 然后暴力拓展，容易证明这样暴力拓展的总次数不会超过 $2n$。

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

P2852，求最长的在 $S_{1\cdots n}$ 中出现至少 $k$ 次的子串的长度。$2\leq k\leq n\leq 20000$。

求出 $height$ 数组，不难发现 $\min\{height_{l+1\cdots r}\}=x$ 代表着后缀 $sa_{l\cdots r}$ 都有长度为 $x$ 的 lcp，并且由于字典序的原因，一个子串反复出现一定会导致每次出现位置对应的后缀在 $sa$ 中连续，那么答案就是 $\max\{\min\{height_{i\cdots i+k-2}\}\}$。$O(n\log n)$，数据水可以 $O(nk)$ 通过原数据。

P4248，求 $\sum_{i<j} \text{lcp}(i,j)$。$n\leq 5\times 10^5$。

$\text{lcp}(sa_i,sa_j)=\min\{height_{i+1\cdots j}\}$。

感性考虑后缀排名从 $sa_i$ 变到 $sa_j$ 的过程，若其始终有长度为 $x$ 的共同前缀，则一定在某两个位置之间会有第 $x+1$ 个位置上的变动，由于字典序相邻所以不会出现第 $x$ 位上的反复横跳。

由于 $sa$ 也是个排列，所以直接拿 $sa_i$ 替换 $i$，要求的就是 $\sum_{2\leq l\leq r\leq n}\min\{height_{l\cdots r}\}$，这是个经典问题，可以用单调栈解决：

int solve(int n){
    int ret=0;
    For(i,1,n){
        while(tp&&a[i]<a[stk[tp]])R[stk[tp--]]=i-1;
        L[i]=stk[tp]+1,stk[++tp]=i;
    }while(tp)R[stk[tp--]]=n;
    For(i,1,n)ret+=(i-L[i]+1)*(R[i]-i+1)*a[i];
    return ret;
}

把 < 改为 > 可求每个区间最大值之和。

SP705，本质不同子串个数。$\frac{n(n+1)}{2}-\sum height_i$。

SP1811，最长公共子串,。$n_1,n_2\leq 2.5\times 10^5$。

把两个串拼在一起求 $height$，遍历 $sa_{1\to n_1+n_2}$，$i$ 找到前面最近的与 $[sa_i\leq n_1]$ 类型不同的 $j$ 进行贡献，注意不能越界。$O(n\log n)$。

P3181，给定串 $S_{1\cdots n},T_{1\cdots m}$，求有多少个 $(len,l_1,l_2)$ 满足 $S[l_1:l_1+len-1]=T[l_2,l_2+len-1]$。$n,m\leq 2\times 10^5$。

记 $calc(S)$ 为 $S$ 中相同子串的个数，则答案为 $calc(S+\text{@}+T)-calc(S)-calc(T)$。注意反复调用 SA 时 rk[n+1] 位置的清空。$O(n\log n)$。

P4070，求 $S$ 每个前缀的本质不同子串个数，不强制在线。$n\leq 10^5$。

考虑离线求出 reverse 后的 $sa$，动态倒着插入 $i$ 到 $rk_i$ 位置，用 STL::set 配合 ST 表维护当前答案（$\sum height_i$）。$O(n\log n)$。

扩展 KMP

字符串下标从 $1$ 到 $n$。exkmp 可以在线性复杂度内求出 $z_i$ 表示 $\text{lcp}(s,s[i:])$，即 $s$ 与每个 $s$ 的后缀的 $\text{lcp}$。

初始 $z_1=n$，另外从 $z_2$ 开始，维护右端点最大的 $[i,i+z_i-1]=[l,r]$，当 $i\leq r$ 时，$[l,r]=[1,r-l+1]$，对应找到 $z_{i-l+1}$ 就是 $[i,r]$ 这一段与 $s$ 的最少的 $\text{lcp}$，但这个值不能超过 $r-i+1$，然后暴力拓展并尝试更新 $[l,r]$，复杂度即为 $O(n)$，考虑简单证明一下复杂度。

• 若有初始值之后不能扩展，即 $z_{i-l+1}<r-i+1$ 一类，则求出这个 $z_i$ 是 $O(1)$ 的。
• 若有初始值之后可以扩展，则 $r$ 会更新，总共更新次数是 $O(n)$ 的，均摊下来也是 $O(1)$。

则类似马拉车地，这么做的复杂度即为 $O(n)$，特殊处理 $z_1$ 的原因是 $[1,n]$ 始终会霸占 $[l,r]$，而 $l=1$，就没有初始值的意义了。

void zalgo(char *s,int* z,int n){
    z[1]=n;for(int i=2,l=0,r=0;i<=n;i++){
        z[i]=0;
        if(i<=r)z[i]=min(z[i-l+1],r-i+1);
        while(i+z[i]<=n&&s[i+z[i]]==s[1+z[i]])z[i]++;
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }
}