SA-IS

· · 算法·理论

前置

\gdef\suf{\mathit{suf}} \gdef\S{\mathtt{S}} \gdef\L{\mathtt{L}} \gdef\P{\mathtt{P}}

记 n=|s|,\suf_i 表示后缀 s[i,n]。

为方便,在 s 最后添加一个最小值字符 s_n=\texttt{*}。

由于要往最后加 \texttt{*},一开始先给 s 最后加个极小值再跑 SA-IS。

SL 型后缀

对于后缀 \suf_i:

特别地,suf_n 为 \S 型。

相同首字符性质

性质:对于后缀 \suf_x,\suf_y,若首字符 s_x=s_y 且 \suf_x,\suf_y 分别为 \S,\L 型,那么 \suf_x>\suf_y。

精炼版:首字符相同的后缀,必定有 \S 型大于 \L 型。

证明:

LMS 位置 & 子串

位置 p>1 是 LMS 位置,当且仅当 \suf_{p-1} 是 \L 型且 \suf_p 是 \S 型。

即每个 \S 连续段的段首是 LMS 位置。

用后缀大小关系来看,LMS 位置 p 满足 \suf_{p-1}>\suf_p<\suf_{p+1}。

显然 n 必定是 LMS 位置。

将 LMS 后缀 s[p,n] 的类型记做 \P,一种特殊的 \S。

相邻两个 LMS 位置 p,q 之间的子串 s[p,q] 为 LMS 子串。

LMS 子串的类型形如:\mathrm{PSS\dots SLL\dots LP}。

相邻两个 LMS 子串首尾共用一个 LMS 位置。

重要引理

引理:

不存在两个 LMS 子串 X,Y 满足:

子串 s[l,r] 的类型串指的是 i=l,\dots,r 的 \suf_i 后缀类型的拼接。

证明:满足条件的 Y_{|X|} 会是 \P 型,而 LMS 子串只有首尾两个 \P,矛盾。

LMS 后缀排序引理

考虑将所有 LMS 子串排序,得到一个 LMS 子串的 rnk。

引理:

将所有 LMS 位置的后缀排序,对于两个后缀 \suf_x,\suf_y:

从 x 开始有若干个 LMS 子串,记序列 X 为这些 LMS 子串的 rnk 值。

同理 y 开始的 LMS 子串求出序列 Y。

必定有:\suf_x,\suf_y 的字典序关系等于 X,Y 的字典序关系。

举个例子:

\begin{aligned} s=\mathtt{baaacbaabac*}\\\mathtt{L\red{P}SSLL\red{P}SL\red{P}S\red{P}} \end{aligned} |LMS 子串|$\mathtt{aaacb}$|$\mathtt{aaba}$|$\mathtt{ac*}$|$\mathtt{*}$| |:-:|:-:|:-:|:-:|:-:| |$rnk$|$1$|$2$|$3$|$4$| LMS 后缀: $$ \begin{aligned} &\mathtt{aaacbaabac∗}&&\{1,2,3,4\}\\ &\mathtt{aabac∗}&&\{2,3,4\}\\ &\mathtt{ac∗}&&\{3,4\}\\ &\mathtt{∗}&&\{4\}\\ \end{aligned} $$ 排序之后: $$ \begin{aligned} &\mathtt{aaacbaabac∗}&&\{1,2,3,4\}\\ &\mathtt{aabac∗}&&\{2,3,4\}\\ &\mathtt{ac∗}&&\{3,4\}\\ &\mathtt{∗}&&\{4\}\\ \end{aligned} $$ 但是发现有个反例: $$ \begin{aligned} s=\mathtt{acbbccbbccbac*}\\\mathtt{SL\red PSLL\red PSLLL\red PS\red P} \end{aligned} $$ |LMS 子串|$\mathtt{bbccb}$|$\mathtt{bbccba}$|$\mathtt{ac*}$|$\mathtt{*}$| |:-:|:-:|:-:|:-:|:-:| |$rnk$|$2$|$3$|$1$|$4$| LMS 后缀: $$ \begin{aligned} &\mathtt{bbccbbccbac∗}&&\{2,3,1,4\}\\ &\mathtt{bbccbac∗}&&\{3,1,4\}\\ &\mathtt{ac∗}&&\{1,4\}\\ &\mathtt{∗}&&\{4\}\\ \end{aligned} $$ 排序之后: $$ \begin{aligned} &\mathtt{ac∗}&&\{1,4\}\\ &\mathtt{bbccbac∗}&&\{3,1,4\}\\ &\mathtt{bbccbbccbac∗}&&\{2,3,1,4\}\\ &\mathtt{∗}&&\{4\}\\ \end{aligned} $$ 怎么回事呢,注意 $\mathtt{bbccb},\mathtt{bbccba}$ 这两个串类型串是 $\mathtt{SSLLP},\mathtt{SSLLLP}$。 我们钦定,**在 LMS 子串是真前缀关系时,字典序比较是比类型串第一个不同位置,$\S$ 者更大。** 因此上面反例的 $rnk$ 实际上是 $\{3,2,1,4\}$。 证明: 考虑两个 LMS 后缀 $\suf_x,\suf_y$ 比较的时候,依次比较它们对应的那些 LMS 子串。 当前比较 $A,B$ 两个 LMS 子串,若 $A=B$ 则比较下两个串直到 $A\ne B$: - 两个串为真前缀关系,修正的字典序定义里,相同首字符性质,$\S$ 者后缀排名更大。 - 两串不为真前缀关系,必定存在不相等的位置,最靠前的为 $p$。 $\{\suf_x,\suf_y\},\{A,B\}$ 字典序比较时都在 $p$ 比出结果。 ## 诱导排序 假设已经用某种方法求出了 LMS 子串的排名 $rnk$。 LMS 位置不相邻,最多 $\left\lceil\dfrac{n}{2}\right\rceil$ 个,递归求解 $rnk$ 的后缀数组 $sa'$。 现在考虑用 $sa'$ 推出原串的 $sa$。$sa'$ 即已知所有 $\P$ 的后缀排名。 先将原串所有后缀按首字母分类开桶,每个桶内,$\L$ 型一定比 $\S$ 型要小。 诱导排序(Induced Sort): - 将已经确定排名的 $\P$ 位置从小到大入桶,即入桶时它是当前桶内最大值。 - 从小到大扫当前已经确定排名的后缀 $\suf_p$,若 $\suf_{p-1}$ 还未确定排名且 $p-1$ 为 $\L$ 型: $\suf_{p-1}$ 加入 $a_{p-1}$ 桶内,它是当前桶内 $\L$ 最大值。 - 清空所有 $\P$ 位置的排名,即假设我只知道 $\L$ 的排名。 - 再从大往小扫已经确定排名的后缀 $\suf_p$,若 $\suf_{p-1}$ 还未确定排名且 $p-1$ 为 $\S$ 型: $\suf_{p-1}$ 加入 $a_{p-1}$ 桶内,它是当前桶内 $\S$ 最小值。 ![](https://s3.bmp.ovh/2026/11/05/T90CH21z.png) $\L$ 型入桶时从左往右填绿块,$\S$ 型入桶时从右往左填蓝块。 由于最后两个 $\P$ 右边可能没有 $\L$,所以中间清除 $\P$ 排名时不清最后两个 $\P$。 最后两个 $\P$ 一定是全局最小值、最大值。(显然递归时还是) 为啥是对的,对于两个首字母相同后缀 $\suf_x,\suf_y$: - $x,y$ 类型不同,诱导排序显然桶内有 $\L$ 比 $\S$ 小 - $x,y$ 都是 $\L$,不妨设 $x$ 先比 $y$ 入桶 - $s_{x+1}=s_{y+1}$,$x$ 比 $y$ 先入桶,肯定是因为 $x+1$ 比 $y+1$ 先入桶,递归比较。 - $s_{x+1}<s_{y+1}$,满足 $\suf_x<\suf_y

LMS 子串排序

现在问题只剩求 rnk 数组了,这一步非常地神。

结论:将 rnk 只按首字母排序,跑诱导排序,得出的 sa 中 LMS 位置的 rnk 即为真 rnk。

只观察最后一个字符,即一开始的按首字母排序,结果是对的。

同上面诱导排序证明,只观察 LMS 子串,求出的 sa 是对的。

实现

inline void SAIS(int*s,int*sa,int n,int sig){
    char t[n+2];
    memset(t,'\0',sizeof(char)*(n+2));
    t[n]='S';
    for(int i=n-1;i;i--)
    {
        t[i]=s[i]==s[i+1]?t[i+1]:(s[i]<s[i+1]?'S':'L');
    }
    static bool lms[MAXN];
    for(int i=2;i<n;i++)
    {
        lms[i]=t[i]=='S'&&t[i-1]=='L';
    }
    lms[n]=true;
    int c=0;
    int p[n/2+2];
    p[0]=0;
    for(int i=1;i<n;i++)
    {
        if(lms[i]){
            p[++c]=i;
        }
    }
    p[++c]=n;
    static int sum[MAXN];
    memset(sum,0,sizeof(int)*(sig+1));
    for(int i=1;i<=c;i++)
    {
        sum[s[p[i]]]++;
    }
    for(int i=1;i<=sig;i++)
    {
        sum[i]+=sum[i-1];
    }
    int rnk[n+1];
    rnk[0]=0;
    for(int i=1;i<=c;i++)
    {
        rnk[i]=sum[s[p[i]]]--;
        sa[rnk[i]]=i;
    }
    auto IS=[&](){
        static int L[MAXN],S[MAXN];
        memset(sum,0,sizeof(int)*(sig+1));
        for(int i=1;i<=n;i++)
        {
            sum[s[i]]++;
        }
        for(int i=1;i<=sig;i++)
        {
            sum[i]+=sum[i-1];
            L[i]=sum[i-1]+1;
            S[i]=sum[i];
        }
        int sa_[c+1];
        memcpy(sa_,sa,sizeof(int)*(c+1));
        memset(sa,0,sizeof(int)*(n+1));
        for(int i=c;i;i--)
        {
            sa[S[s[p[sa_[i]]]]--]=p[sa_[i]];
        }
        for(int i=1;i<=n;i++)
        {
            if(sa[i]>1&&t[sa[i]-1]=='L'){
                sa[L[s[sa[i]-1]]++]=sa[i]-1;
            }
        }
        for(int i=c;i;i--)
        {
            sa[++S[s[p[sa_[i]]]]]=0;
        }
        sa[S[s[p[c]]]--]=p[c];
        for(int i=n;i;i--)
        {
            if(sa[i]&&t[sa[i]-1]=='S'){
                sa[S[s[sa[i]-1]]--]=sa[i]-1;
            }
        }
    };
    IS();
    int k=0;
    for(int i=1,j=0;i<=n;i++)
    {
        auto chk=[&](int x,int y){
            if(s[x]^s[y]){
                return false;
            }
            x++;
            y++;
            while(!lms[x]||!lms[y])
            {
                if(lms[x]||lms[y]||s[x]^s[y]){
                    return false;
                }
                x++;
                y++;
            }
            return true;
        };
        if(lms[sa[i]]){
            int x=sa[i];
            k++;
            if(j&&chk(j,x)){
                k--;
            }
            j=x;
            rnk[x]=k;
        }
    }
    for(int i=1;i<=c;i++)
    {
        rnk[i]=rnk[p[i]];
    }
    if(k==c){
        for(int i=1;i<=c;i++)
        {
            sa[rnk[i]]=i;
        }
    }
    else{
        SAIS(rnk,sa,c,k);
    }
    IS();
}
inline void SA(){
    static int S[MAXN];
    for(int i=1;i<=n;i++)
    {
        S[i]=s[i];
    }
    S[n+1]=1;
    S[n+2]=128;
    SAIS(S,sa,n+2,128);
    for(int i=1;i<=n;i++)
    {
        sa[i]=sa[i+1];
    }
}

OI-Wiki 上有个卡空间到极致的做法:最优原地后缀排序算法

效率

时间复杂度 T(n)=T\!\left(\dfrac{n}{2}\right)+O(n)=O(n)。

但是 IS 虽然是线性但是非常慢,实测 n=10^7 跑一遍 IS 就要 0.5\mathrm s。

但总体来说高贵的线性还是会比极限卡常的单 \log 快。

QOJ 板题:单 \log 评测记录,SA-IS 评测记录

参考文献