后缀数组自闭笔记

省选前最后两周。同时也是退役前最后两周。

在 wzx 的鼓动下开了字符串。

然后自闭了。

以下，我们约定，$S_{l,r}$ 表示字符串 $S$ 下标为 $[l,r]$ 的子串，下标从 $1$ 开始。超过串长的部分用小于其他所有字符的空字符填充。

后缀排序

std::sort（光速逃

不过 std::sort 也是可以做的（

我们发现，这种做法的瓶颈在于比较两个后缀的大小。我们可以二分 +Hash 求出它们的最长公共前缀的长度，然后比较这个前缀后一个字符的大小。这么做的时间复杂度是 $O(n\log^{2}n)$ 的。

但是没什么用（

然后我们就需要用到后缀数组（Suffix Array）了。

SA 一共有四种构建方式，分别是 $O(n\log n)$ 的倍增，$O(n)$ 的 DC3 和 SA-IS，以及 $O(1)$ 的潮爷排序。但是后三种太高端了我都不会（

假设对于每一个位置 $i$，我们已经按照 $S_{i,i+k-1}$ 的大小排好了序，并且有了一个排名。我们以 $i$ 的排名为第一关键字，$i+k$ 的排名为第二关键字，排一遍序，整个字符串就被按照 $S_{i,i+2k-1}$ 的大小排好了序。当所有位置的排名都不同时，说明整个过程可以结束了。

但是问题来了，排一遍序不是 $O(n\log n)$ 的吗（

我们有基数排序啊（

// s[i]：原字符串
// fst[i]：后缀 i 的第一关键字
// snd[i]：第二关键字排名为 i 的后缀
// tak[i]：桶
// sa[i]：排名为 i 的后缀
// 一开始时以首字符为第一关键字，位置为第二关键字排序
for(re int i=1;i<=n;++i)
     ++tak[fst[i]=s[i]];
for(re int i=1;i<=122;++i)
     tak[i]+=tak[i-1];
     // 处理桶内前缀和，用来求出第一关键字为 i 的后缀的最大可能排名
for(re int i=n;i>=1;--i)
     sa[tak[fst[i]]--]=i;
     // 第一关键字相同时，第二关键字排名越大总排名越大，因此倒序枚举
     // 因为第二关键字是位置，所以 snd[i]=i
for(re int mx=122,k=1;;k<<=1){
     re int cnt=0;
     for(re int i=n-k+1;i<=n;++i)
         snd[++cnt]=i;
         // (n-k,n]的这些后缀没有第二关键字，因此排名最靠前
     for(re int i=1;i<=n;++i)
         if(sa[i]>k)
             snd[++cnt]=sa[i]-k;
     for(re int i=1;i<=mx;++i)
         tak[i]=0;
     for(re int i=1;i<=n;++i)
         ++tak[fst[i]];
     for(re int i=1;i<=mx;++i)
         tak[i]+=tak[i-1];
     for(re int i=n;i>=1;--i)
         sa[tak[fst[snd[i]]]--]=snd[i];
     for(re int i=1;i<=n;++i)
         snd[i]=fst[i];
         // 因为要生成下一轮排序时的第一关键字，把 fst 里的信息先扔到 snd 里
     for(re int i=1;i<=n;++i)
         fst[sa[i]]=fst[sa[i-1]]+(snd[sa[i]]!=snd[sa[i-1]]||snd[sa[i]+k]!=snd[sa[i-1]+k]);
         // 如果当前后缀与前一个后缀相同则共用排名，否则 +1
     if(fst[sa[n]]==n)
         break;
     else
         mx=fst[sa[n]];
}

看上去非常的绕（

最后直接输出 sa 数组即可。

rnk 数组

rnk[i] 表示排名为 $i$ 的后缀。

不难发现 rnk[sa[i]]=sa[rnk[i]]=i。

het 数组

大概算是 SA 的重点。

令 lcp(x,y) 表示 $x,y$ 两个后缀的最长公共前缀（Longest Common Prefix）的长度。

het[i] 就被定义为 lcp(sa[i],sa[i-1])。het[1]=0。

不难发现 lcp(x,z)=min(lcp(x,y),lcp(y,z))(x<y<z)，lcp(x,y)=min{lcp(i,i-1)}=min{het[i]}(rnk[x]<i<=rnk[y])。

那么问题来了，怎么求呢（

首先我们是肯定不能暴力枚举的。

二分 +Hash？太麻烦而且复杂度不够优秀（

SA 的 het 数组有一个性质，就是 het[rnk[i]]>=het[rnk[i-1]]-1。

我们只考虑 het[rnk[i-1]]>0 时的情况。

令 k=sa[rnk[i-1]-1]，lcp(i-1,k)=het[rnk[i-1]]，又因为后缀 $i$ 是后缀 $i-1$ 删去首字符得到的，后缀 $k+1$ 是后缀 $k$ 删去首字符得到的，从而 lcp(i,k+1)=het[rnk[i-1]]-1。

后缀 $i-1$ 比后缀 $k$ 大，删去首字符后，后缀 $i$ 肯定也比后缀 $k+1$ 大。根据 lcp 的性质我们有 lcp(i,sa[rnk[i]-1])>=lcp(i,k+1)，也即 het[rnk[i]]>=het[rnk[i-1]]-1。

利用这个性质，我们就可以在 $O(n)$ 的时间复杂度内求出 het 数组了。

for(re int i=1,j=0;i<=n;++i)
     if(rnk[i]>1){
         j-=!!j;
         re int pos=sa[rnk[i]-1];
         for(;i+j<=n&&pos+j<=n&&s[i+j]==s[pos+j];++j);
         het[rnk[i]]=j;
     }

然后 SA 就彻底建好了。没错就这么点东西（

板子应用

不同子串个数

给定一个长度为 $n$ 的字符串 $S$，求其本质不同的子串的数量。

首先有一个很显然的结论是，如果一个字符串是 $S$ 的子串，那么它一定是 $S$ 的若干个排名连续的后缀的公共前缀。

对于排名为 $1$ 和排名为 $2$ 的两个后缀来说，它们一共有 het[2] 个公共前缀；排名为 $2$ 和排名为 $3$ 的两个后缀一共有 het[3] 个公共前缀……

因此，$S$ 的不同子串个数就是它的所有子串个数，$\cfrac{n(n+1)}{2}$，减去所有 het 的和。

最长公共子串

给定 $n$ 个字符串 $S_{1},S_{2},\cdots,S_{n}$，求它们的最长公共子串。

我们首先将这 $n$ 个串拼在一起，中间插入特殊字符将相邻的两个串隔开。然后我们将每个串内部的字符染色，第 $1$ 个串染成颜色 $1$，第 $2$ 个串染成颜色 $2$，用尺取法找出 sa[l],sa[l+1],...,sa[r] 覆盖全部 $n$ 种颜色的区间 $[l,r]$，求出其中 min{het[i]}(l<i<=r) 的最大值即可。

模式串出现次数

给定 $n$ 个文本串和 $m$ 个模式串，询问每个模式串在 $n$ 个文本串中一共出现了多少次。

首先将所有文本串拼在一起。对于每一个模式串，如果我们能够找到这个长串的任意一个后缀 $x$，使得其拥有这个模式串作为前缀，然后找到一个最小的 $l$ 和一个最大的 $r$，使得 min{het[i]}(l<i<=rnk[x]) 和 min{het[i]}(rnk[x]<i<=r) 均大于等于该模式串长度，$r-l+1$ 就是答案。不难看出向两边取 $\min$ 这个操作具有单调性，因此我们可以二分。

但是问题来了，我们该怎么找到这个后缀啊。

一想，把模式串也接到文本串后就可以了。

那如果说模式串出现了互相包含的情况呢？

我们可以再开一个数组 col，col[i] 表示 sa[i] 的首字符是否属于一个文本串。因为这个是静态的，直接一遍前缀和就行。

母串数量

给定 $n$ 个文本串和 $m$ 个模式串，询问每个模式串在多少个文本串中出现过。也就是说，在同一个文本串中出现多次只记一次。

和上面一样，只不过是最后一步 col[i] 表示 sa[i] 的首字符所属的文本串的编号，对于每一个模式串，二分出区间后数一下颜色种类数。

课后习题

自己找去吧（

然后您就会发现字符串的题一道比一道神仙（