后缀数组基础

OIer_FY · 2023-04-28 19:26:26 · 个人记录

PDF

后缀数组 sa 和排名数组 rk

例题一：后缀排序。

设 sa_i 为把字符串 s 的所有后缀排序后，排名第 i 的后缀。例题要求的就是 sa.

设 rk_i 为把字符串 s 的所有后缀排序后，后缀 i 的排名。

根据定义，得

求 sa 和 rk（\operatorname O(n \log n)）

如果直接排序是 \operatorname O(n^2\log n) 的，不能接受。

注意到我们排序的元素有一些“包含”。使用倍增思想来排序。

设 rk_{w,i} 为子串 s_{i\sim i+2^w-1} 的排名。那么每次倍增合并后缀的排名，使用双关键字排序，最后得出的就是 rk 数组。

如图所示（《后缀数组——处理字符串的有力工具》，有改动）

那么内层排序我们使用基数排序和计数排序，就可以实现 \operatorname O(n \log n) 排序。

小优化：发现第二关键字无需计数排序，可以直接按值加入（详见代码）。

m = 256; // m refers to the maximum of the value of rk
for (int i=1; i <= n; i++) b[rk[i] = s[i]]++; // b is a bucket
for (int i=1; i <= m; i++) b[i] += b[i-1];
for (int i=n; i >= 1; i--) sa[b[rk[i]]--] = i;

for (int w=1; w <= n; w <<= 1)
{
    // The first key word is rk[i] while the second is rk[i+w]
    // The second key word doesn't need counting sort
    int c0 = 0;
    for (int i=n-w+1; i <= n; i++) c[++c0] = i; // [n-w+1,n] don't have the second key word, so they're the smallest
    for (int i=1; i <= n; i++) // i refers to the value of the second key word
        if (sa[i] > w) c[++c0] = sa[i]-w; // sa[i] is the position of i
    // Then we get an array c sorted by the second key word

    // Sort the first key word
    clear(b);
    for (int i=1; i <= n; i++) b[rk[i]]++;
    for (int i=1; i <= m; i++) b[i] += b[i-1];
    for (int i=n; i >= 1; i--) sa[b[rk[c[i]]]--] = c[i]; // Two-key-word counting sort
    memcpy(old,rk,sizeof old); // old rk

    // Compute new rk
    for (int i=1; i <= n; i++)
    {
        if (old[sa[i]] == old[sa[i-1]] && old[sa[i]+w] == old[sa[i-1]+w]) rk[sa[i]] = rk[sa[i-1]];
        else rk[sa[i]] = rk[sa[i-1]]+1;
    }
}

简单应用

例题二：字符加密。

题目大意：求字符串 s 最小的循环同构串。

把原字符串复制一遍，就变成了后缀排序问题。

例题三：【模板】AC自动机。

题目大意：给出文本串 s 和多个模式串 t_i，求 t 在 s 中有没有出现。

因为我找不到别的题了，所以就只能用这一题。

若 t_i 在 s 中有出现，那么它一定是一个后缀的前缀。那么我们在 sa 上二分，找到最小的 \geqslant t_i 的后缀即可。

时间复杂度为 \operatorname O(|t_i|\log n)，比 AC 自动机多一个 \log，但是在线。

高度数组 height（以下有时简称为 h）

设 height_i=\text{lcp}(sa_i,sa_{i-1})，即排名第 i 的后缀和排名第 i-1 的后缀的最长公共前缀（的长度） 。

求 height 数组

引理一

证明：当 h_{rk_{i-1}}\leqslant 1 时，引理成立。

当 h_{rk_{i-1}}\geqslant 1 时，即 \text{lcp}(i-1,sa_{rk_{i-1}-1})\geqslant 1.

设后缀 i-1 为 \texttt{aAC}，后缀 sa_{rk_{i-1}-1} 为 \texttt{aAB}，其中 \texttt{a} 为一个字符，\texttt{A}、\texttt{B}、\texttt{C} 均为子串，\texttt{B} 可为空。显然 \texttt{B} < \texttt{C}.

则后缀 i 为 \texttt{AC}. 所以 \texttt{AB} < \texttt{AC} = 后缀 i.

又因为后缀 sa_{rk_{i}-1} 是最大的小于后缀 i 的后缀，所以 \texttt{AB}\leqslant sa_{rk_i-1} <\texttt{AC}= 后缀 i.

所以 \text{lcp}(i,sa_{rk_i-1})\supseteq\texttt{A}. 所以 h_{rk_i}\geqslant h_{rk_{i-1}}-1.

那么有了这个引理，就可以求出 height 数组了。

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