后缀数组从入门到进门

后缀自动机（SAM）则是一种强有力的数据结构，用于解决有关字符串的很多东西。一般复杂度是 $\mathcal{O}(n)$ 的。因为写博客的时间原因 SAM 暂时咕着。暂时只讨论 SA。

本文可能出现的部分词语定义如下：

后缀：字符串 $s$ 的后缀，定义为字符串的某个位置到字符串末尾的子串。特别的，称从第 $i$ 个字符为第一个元素的后缀为第 $i$ 个后缀。
前缀：基本同后缀，只是定义为从字符串第一个字符到某个位置的子串。
后缀的排名：定义第 $i$ 个后缀的排名，为字符串所有后缀按字典序排序后，第 $i$ 个后缀的排名。
LCP：定义 $\mathrm{LCP}(i,j)$ 为一个字符串排名为 $i$ 的后缀和排名为 $j$ 的后缀的最长公共前缀，有时只最长公共前缀长度，本文也是如此，有的地方指最长公共前缀，有的地方指最长公共前缀长度。
字符串的大小关系：两个字符串比较大小，默认是比较字典序谁先谁后。

一些变量含义：

$sa_i$ 表示排名为 $i$ 的后缀是 $s$ 的第几个后缀。
$rk_i$ 表示 $s$ 的第 $i$ 个后缀的排名。

此外，在后文中，如果没有特殊定义，则 $s$ 表示需要处理的字符串，

后缀数组

build

$s$ 的第 $i$ 个后缀的长度为 $n-i+1$ 。用 string 记录后缀的时候，可以直接 size 来判断这是第几个后缀，非常方便。

此外有显而易见的结论： $rk_{sa_i} = sa_{rk_i} = i$ 。

后缀数组最核心的地方就是如何得到 $sa,rk$ 。以及如何用这两个数组求出题目所求。

首先按每个后缀的第一个字符排序。对于每一个后缀，按照第一个字符的字典序可以给它一个临时排名。这个临时排名显然有可能并列。因为不同后缀的第一个字符可能是相同的。

然后把相邻的字符拼在一起，也就是每个后缀的前两位进行排序。考虑到我们已经排过第一位了，而第一位小的第二位不管怎样这个后缀整体都小，也就是这个时候可以直接只把并列的部分拿出来，然后按照第二位排序就行。如果嫌麻烦，也可以直接按照临时排名为排序第一关键字，第二位上的字符为第二关键字。

这时得到了新的临时排名（更新之前的临时排名），此时再把相邻的两个拼在一起，也就是每个后缀的前四位进行排序。考虑到任意连续的两个字符拼在一起的排名已经出来了。这一次排序可以按照前两个字符排名为第一关键字，后两个字符排名为第二关键字。进行排序。

以此类推排序，上一次按照前 $x$ 个字符排序，这一次就按照前 $2x$ 个字符排序。在什么时候结束呢？很显然，如果这一次得到的临时排名没有出现并列，说明这个时候的排名已经是非常严谨的最终排名了。按照这种排序方法显然不会出问题。此时的排名就是最终的 $rk$ 数组。然后根据 $rk$ 推 $sa$ 。

这样整体的排序，sort 的 $n\log n$ 还在，但是变成了双关键字排序，也就是单次比较大小是 $\mathcal{O}(1)$ 的。因为最坏要排序 $\log n$ 次。因此整体复杂度 $n\log^2 n$ 。还是有点慢，但是基数排序就可以做到 $n\log n$ 了。

struct SA{
    int rk[max_n],sa[max_n],tp[max_n],m;
    SA(){m=300;memset(sa,0,sizeof(sa));} // m 表示桶大小
    
    inline void sort(){ // 基数排序
        memset(sm,0,sizeof(sm));
        for(register int i=1;i<=n;++i)
            ++sm[rk[i]];
        for(register int i=1;i<=m;++i)
            sm[i]+=sm[i-1]; 
        for(register int i=n;i>=1;--i){
            sa[sm[rk[tp[i]]]]=tp[i],
            --sm[rk[tp[i]]];
        }
    }
    inline void build(int a[]){ // 建 SA，a 数组是原串
        for(register int i=1;i<=n;++i){
            rk[i]=a[i],
            tp[i]=i; // tp[i] 表示第二关键字排名为 i 的后缀的第一关键字位置
        }
        sort();

        int len=1;
        while(1){ // 倍增
            int cnt=0;
            for(register int i=1;i<=len;++i)
                tp[++cnt]=n-len+i;
            for(register int i=1;i<=n;++i)
                if(sa[i]>len)
                    tp[++cnt]=sa[i]-len;
            sort(),
            memcpy(tp,rk,sizeof(rk));
            rk[sa[1]]=cnt=1;
            for(register int i=2;i<=n;++i){
                if(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+len]==tp[sa[i-1]+len])
                    rk[sa[i]]=cnt;
                else
                    rk[sa[i]]=++cnt;
            }
            m=cnt,len<<=1;
            if(cnt>=n) break; // 说明没有并列，已经排好了
        }
    }
}sa;

getlcp

首先要考虑 LCP 有什么性质。根据 LCP 的定义，有这样两个显然的性质：

$\mathrm{LCP}(i,j) = \mathrm{LCP}(j,i)$ 。
记 $len_i$ 表示排名为 $i$ 的后缀的长度，有 $\mathrm{LCP}(i,i)=len_i$ 。

这样，计算 LCP 时，对于 $i>j$ 的情况，可以转化为 $i<j$ 的情况做。对于 $i=j$ 的情况，直接用 $sa_i$ 算就行。简化了代码实现的复杂程度。

\mathrm{LCP}(i,j) = \min_{i\leq k\leq j} (\mathrm{LCP}(i,k),\mathrm{LCP}(k,j))

证明

设 $p = \min(\mathrm{LCP}(i,k),\mathrm{LCP}(k,j))$ ， $a$ 为 $s$ 的第 $sa_i$ 个后缀， $b$ 为 $s$ 的第 $sa_j$ 个后缀， $c$ 为 sss 的第 $sa_k$ 个后缀。

所以 $a,c$ 的前 $p$ 个字符相同， $b,c$ 的前 $p$ 个字符相同。所以 $a,b$ 的前 $p$ 个字符相同。所以有 $\mathrm{LCP}(i,j)\geq p$ 。

设存在 $q$ $\mathrm{LCP}(i,j) = q>p$ ，此时一定会有 $a_{[1,q]} = b_{[1.q]}$ ，也就有 $a_{p+1} = b_{p+1}$ 。这与 $p=\min(\mathrm{LCP}(i,k),\mathrm{LCP}(k,j))$ 矛盾。

上面这个定理简单推导可以得到一个更常见的形式：

\mathrm{LCP}(i,j) = \min_{i\leq k\leq j} (\mathrm{LCP}(k,k-1))

下面考虑求 LCP。

注意到 $\mathrm{LCP}(i,i) = len_i = n-sa_i+1$ 。这个是可以快速求出的。然后根据 LCP 定理，设 $ht_i = \mathrm{LCP}(i,i-1)$ ，其中 $ht_1=0$ ，那么有：

\mathrm{LCP}(i,j)= \min_{i\leq k\leq j}(ht_k)

求 $ht$ 的过程需要考虑两个 $ht$ 之间的关系。不妨定义 $h_i = ht_{rk_i}$ ，显然有 $ht_i = h_{sa_i}$ 。然后考虑一个非常重要的定理：

h_i\geq h_{i-1} -1

证明比较复杂，可以在这个博客里看到。这个性质保证了 $h_i$ 要么是 $h_{i-1}-1$ 要么不降，可以 $\mathcal O(n)$ 递推得到。

// a 数组是原串
for(register int i=1,j=0;i<=n;++i){
    if(j) --j; // h[i]>=h[i-1]-1
    int k=sa[rk[i]-1];
    while(a[i+j]==a[j+k])
        ++j;
    ht[rk[i]]=j; // h[i]=ht[rk[i]]
}

有这样求可以非常好地求出 LCP 了。如果用稀疏表这样的 DS 维护 $ht$ ，就可以 $n\log n$ 预处理， $\mathcal O(1)$ 查询。

$ht$ 与 LCP 在题目中的应用可以说是相当灵活的，通常需要自行找到一些相关的性质。不过这三个例子或许可以给你一些思考的灵感，你可以记住它们：

最长可重叠重复子串： $ht$ 数组的最大值。
最长不可重叠重复子串：二分答案 $x$ ，对 $ht$ 划分连续段使得每段的最小值不少于 $x$ 。枚举一段，记录最大长度和最小长度 $mx,mn$ ，若 $sa_{mx} - sa_{mn}\geq x$ 则合法。
本质不同的子串数量：枚举每一个后缀，设后缀长度为 $len$ ，第 $i$ 个后缀对答案的贡献为 $len-sa_i+1-ht_i$ 。