后缀数组 \(\text{Suffix Array}\)

参考资料：洛谷日报 #273 浅谈后缀数组算法、常见字符串算法 by Alex_Wei

后缀排序

使用一种基数排序结合倍增的方法，将一个字符串的所有后缀排序。
定义 \(sa_i\) 为排名为 \(i\) 的后缀起始位置，\(rk_i\) 为起始位置为 \(i\) 的后缀排名。
假设已然排出长度为 \(l\) 的全部子串，那么长度为 \(2\times l\) 的只需要按照前半排名为第一关键字，后半排名的第二关键字。
于是以长度为 \(l\) 的排名为参照，可以先按照后半段的排名得到一个结果，在此基础上按照前半段排序。

int n;
char s[maxn];
int sa[maxn],rk[maxn<<1],cnt[maxn],oldsa[maxn],oldrk[maxn<<1],tmp[maxn];
inline void get_sa(){
    int m=max(n,127);
    for(int i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
    for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
    for(int l=1,k;l<n;l<<=1){
        //以上一次排序的rk作为参考
        //先按照后半段排序
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i) oldsa[i]=sa[i];
        for(int i=1;i<=n;++i) ++cnt[rk[oldsa[i]+l]];
        for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        //基数排序要保留原有的关键字，因此从后向前枚举排名
        for(int i=n;i>=1;--i) sa[cnt[rk[oldsa[i]+l]]--]=oldsa[i];
        //同理按照前半段排序
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i) oldsa[i]=sa[i];
        for(int i=1;i<=n;++i) ++cnt[rk[oldsa[i]]];
        for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i) sa[cnt[rk[oldsa[i]]]--]=oldsa[i];
        for(int i=1;i<=n;++i) oldrk[i]=rk[i];
        //现在可以得到基本的顺序，大致知道排名，同时要按照这个排名为另一个数组赋值
        k=0;
        for(int i=1;i<=n;++i){
            //如果两个关键字完全相同排名应当一致
            if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+l]==oldrk[sa[i-1]+l]) rk[sa[i]]=k;
            else rk[sa[i]]=++k;
            if(k==n) return;
        }
        m=k;
    }
}

这里每次倍增都使用的两次基数排序，然而按照后半段时已经没有必要保留原来的顺序，因此分两部分排序：后半段为空的直接放在排名最靠前的位置，剩下的根据后半段的排名依次放进去。
在此基础上进行第二次的基数排序，相当于常数优化，复杂度仍是 \(O(n\log n)\)。

int n;
char s[maxn];
int sa[maxn],rk[maxn<<1],cnt[maxn],oldsa[maxn],oldrk[maxn<<1],tmp[maxn];
inline bool cmp(int x,int y,int l){
    return oldrk[x]==oldrk[y]&&oldrk[x+l]==oldrk[y+l];
}
inline void get_sa(){
    int m=max(n,127);
    for(int i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
    for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
    for(int l=1,k;;l<<=1){
        k=0;
        //后半部分为空直接加入
        for(int i=n;i+l>n;--i) oldsa[++k]=i;
        //剩下的按排名从小到大枚举起始位置超过l的加入
        for(int i=1;i<=n;++i) if(sa[i]>l) oldsa[++k]=sa[i]-l;
        //正常的基数排序
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i) ++cnt[tmp[i]=rk[oldsa[i]]];
        for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i) sa[cnt[tmp[i]]--]=oldsa[i];
        for(int i=1;i<=n;++i) oldrk[i]=rk[i];
        k=0;
        for(int i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],l)?k:++k;
        if(k==n) return;
        m=k;
    }
}

求 \(\operatorname{lcp}\)

\(\operatorname{lcp}(i,j)\) 定义为后缀排序之后，排名为 \(i\) 的后缀与排名为 \(j\) 的后缀的最长公共前缀。
显然后缀排序后，排名越靠近的越相像，可以理性理解即得到：

也就是在已知排名相邻的 \(\operatorname{lcp}\) 后，可以借助数据结构快速求出任意的 \(\operatorname{lcp}\)，目前预处理复杂度已经降到了 \(O(n^2)\)。
这里定义相邻的 \(\operatorname{lcp}\) 为 \(height_i=\operatorname{lcp}(i-1,i)\)，辅助引入一个 \(h_i=height_{rk_i}\)，接下来证明：\(h_i\ge h_{i-1}-1\)。
考虑后缀 \(i\) 实际是后缀 \(i-1\) 去掉第一个字符，假设后缀 \(i-1\) 排名前一位后缀是 \(j-1\)，那么 \(h_{i-1}-1=\operatorname{lcp}(rk_i,rk_j)\)，考虑 \(i-1\) 与 \(j-1\) 都去掉开头字符后，得到的两个后缀的排名距离不会缩小。
也就是说，\(\operatorname{lcp}(rk_i,rk_j)\) 应当是一个多个相邻 \(\operatorname{lcp}\) 取 \(\min\) 的结果。而在这其中，就包括了 \(\operatorname{lcp}(rk_i-1,rk_i)=h_i\)，即证：\(h_i\ge h_{i-1}-1\)。
由于只回退 \(O(n)\) 次，只增加 \(O(n)\) 次，求 \(height\) 数组就是 \(O(n)\) 的。

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;
}

一些技巧

• 求出 \(heihgt\) 后基本上可以把 \(\operatorname{lcp}\) 转化成与区间 \(\min\) 有关的问题。
  最基本的是 \(O(1)\) 查询的 \(\text{ST}\) 表，可以快速求得 \(\operatorname{lcp}\)。
  其次统计所有 \(\operatorname{lcp}\) 时，一共 \(O(n^2)\) 对后缀只有 \(O(n)\) 个答案，于是枚举这些答案的影响范围，实际就是单调栈求作为最小值的区间。
  还有一种操作是考虑对排名相邻的连边权为 \(height\) 的边，任意 \(\operatorname{lcp}\) 都是树上路径的 \(\min\)，类似瓶颈路问题。求与 \(\operatorname{lcp}\) 值对应方案数，考虑从大到小连边，两棵树彼此之间的 \(\operatorname{lcp}\) 都是当前连边的边权。同时可以考虑重构树，新建节点的权值代替边权。

一些题

CodeForces-822E Liar *2400

贪心的去想，且找到一个符合 \(\text{dp}\) 的状态设计。
\(k\) 很小，可以枚举。显然 \(s\) 中同一段前缀，能分段匹配 \(t\) 的前缀越多越好，于是可以 \(\text{dp}\) 的目标就是分段匹配到的最大前缀。
找到 \(j-1\) 次分段后 \([1,i]\) 匹配到的位置 \(p\)，从 \(i+1\) 开始分出一段，需要求两个串从固定位置开始的最大公共子串，加一个分隔符求一下 \(\operatorname{lcp}\) 就好了。
由于是分段匹配，\(dp_{i,j-1}\) 中并不要求 \(i\) 是最后一段的结尾，而转移到的 \(dp_{i+\operatorname{lcp},j}\) 与之相反，解决方法是取前缀 \(\max\)。

洛谷-P1117 [NOI2016] 优秀的拆分

神仙题。
第一步转化是 \(\text{AABB}\) 的形式相当于两个 \(\text{AA}\) 拼接，只需求出每个位置作为 \(\text{AA}\) 的开头或结尾的方案数，答案就是 \(\sum_{i=1}^{n-1} f_ig_{i+1}\)。
之后是非常强大的做法：枚举长度设置关键点。假设当前的 \(|text{A}\) 长度为 \(L\)，当我们每 \(L\) 个位置设置一个关键点时，满足 \(\text{AA}\) 的串一定包含两个关键点，考虑求出这两个关键点 \(\operatorname{lcs}\) 以及 \(\operatorname{lcp}\)，当二者的公共部分区间有交集时，说明至少存在一个 \(\text{AA}\)，简单计算可以确定开头的取值区间和结尾的取值区间。
求 \(\operatorname{lcs}\) 以及 \(\operatorname{lcp}\) 可以正反 \(\text{SA}\)，区间加最后单点查询直接差分即可。

洛谷-P2178 [NOI2015] 品酒大会

结合图论去思考，\(\operatorname{lcp}\) 取 \(\min\) 的性质不仅适合 \(\text{ST}\) 表、单调栈等等数据结构，也可以考虑树上瓶颈路的问题。
即对于将 \(height\) 值作为边权，从大到小连边，每次连边的两个连通块之间的 \(\operatorname{lcp}\) 就是当前枚举边的边权，合并过程中即可维护方案数以及最大乘积。

洛谷-P4248 [AHOI2013]差异

\(\operatorname{lcp}\) 的来源是某个 \(height\)，\(height\) 的贡献是作为最小值的区间，单调栈解决问题。

洛谷-P7409 SvT

多测且选取的范围为集合，对直接查询和单调栈并不友好，考虑使用与瓶颈路有关的做法。
建出重构树后，对于非叶子节点，其权值与左右子树大小之积就是贡献。由于只需要在有左右儿子的节点贡献答案，建虚树即可。

CodeForces-1073G Yet Another LCP Problem *2600

同上，建出虚树后改变一下求解的式子即可。

洛谷-P5028 Annihilate

先插分隔符求出做总的后缀排序。
对于每个位置，钦定其最小值来源的串，那么一定是找到排名的前驱后继求解，使用 set 以及 \(\text{ST}\) 表。这样的复杂度是 \(O(n|s|\log|s|)\)。
这样的做法不够优秀，主要是分开枚举两个后缀的来源限制了复杂度。假定一个后缀的来源，对应的后缀在排名中打上标记，那么每个没有被打上标记的（即来自别的串的后缀），与当前串所有后缀的最大 \(\operatorname{lcp}\) 同样也是在找前驱后继，于是直接正反各扫一遍，每个位置的答案更新为到上一个标记点的答案，时间复杂度是 \(O(|s|\log|s|+n|s|)\)。
分隔符不能使用同样的。

洛谷-P2852 [USACO06DEC]Milk Patterns G

同样处理瓶颈路的套路，出现次数等价于连通块的大小。

后缀自动机 \(\text{Suffix Automaton}\)

明年再说