后缀数组

Vision271 · 2022-07-21 08:37:25 · 个人记录

概述

• 后缀数组是将原字符串的各后缀按字典序排序后所得顺序的记录。
• 利用后缀数组，我们可以方便地做各种字符串操作。
• 我们约定，字符串下标从 1 开始，后缀 i 和 s_i 都表示从下标为 i 的字符开始的后缀，即 s_{i\sim n}，其中 n 为字符串长度。至于 s 的第 i 位处的字符，我们用 s[i] 来表示。
• 不是我不想从 0 开始，但是那样写的话会有各种边界问题（毕竟空串 rk=0，从而有诸如 sa[0],rk[0],sa[?]=0,rk[?]=0 的恶心东西要判），我尝试了 3h 后放弃了。

构成

• 后缀数组主要由两个数组构成：
• 容易看出，sa_{rk_i}=rk_{sa_i}=i。即，rk 是一个正向映射，sa 是一个反向映射。
• 更详细地讲，并不存在一个字符串数组 sorted 来存储“排序后的各个后缀”。rk_i 表示的是 s_i 在这个不存在的 sorted 中的下标。sa_i 表示的是这个不存在的 sorted_i 在 s 中对应哪个 s_i。
• 但是，两者有本质区别：sa 是一个严格映射，rk 是一个非严格映射。之所以最后会变成都是严格的，那是因为各个后缀在长度正确后必然本质不同。

构造

• 下面谈一下怎么构造后缀数组。
• 1.纯暴力
• 2.基于倍增
  • 先对从每个 i 开始，长度为 1 的子串（也即长度为 1 的后缀）排序。
  • 考虑把长度为 2 的子串视为由长度为 1 的子串拼接而成的。
  • 则我们可以把它的两个“组成元素”（两个长度为 1 的子串）的序分别视为排序的第一和第二关键字。
  • 如图所示，每一层基于上一层的排序结果，倍增地排过去。
• 3.倍增+基数-计数排序
  • 关于基数排序和计数排序，请参看"排序"。
  • 从上面的推导我们知道，本排序是双关键字的，而且关键字的值域不大（至多 n）。
  • 从而我们可以开一个 n 的计数桶，然后用基数排序来做。
  • 具体来讲，先对第二关键字计数排序，然后对第一关键字计数排序（都是稳定的）。
  • 每层的排序总复杂度很显然是 O(n) 级别的，严谨地讲是 O(\sum\limits_{i=1}^2 (w_i+n))=O(4n)。
  • 而我们要进行 \log n 层的排序，从而总复杂度降低到了 O(n\log n)。
• 4.SA-IS，DC3 等后缀数组科技
  • 可以实现 O(n) 地构造后缀数组。
  • 实现原理复杂而冗长（肯定不是省选及以下的知识点吧），实际应用中后缀数组类题目的复杂度瓶颈也往往不在后缀数组构造（其他操作已经将复杂度卡在了 n\log n 级别），所以这一部分我们就只是摆在这里。

实现原理

• 这里着重讲一下 O(n\log n) 算法的实现。
• 图很直观，但代码却不那么好写。
• 我们考虑这样一种转移顺序：
  • 先保证 rk 不变。注意，排序结束前的 rk 和结束后的 rk 除了长度差异外还有别的差异：结束前的 rk 是可重的。或者说，两者其实都是可重的，但排序完全结束后的各个后缀必然是本质不同的。
  • 用上一次的 sa 按序在第二关键字意义下计数排序，得到一个临时的 sa' 表示：各个总串第二关键字意义下的 sorted 的 sa。
  • 然后再按 sa' 的序放进取对第一关键字计数排序，同一个桶应当是稳定的。
  • 最后用 sa 更新 rk。
  • 更具体的，看代码吧...

int sa[maxn],id[maxn],rk[maxn],oldrk[maxn],cnt[maxn];
/*
sa[i]:排序后排名为 i 的前缀在原数组是 s_? 
rk[i]:原前缀 s_i 在排序后数组的下标或者说排名
sa是不重的，但是rk是重的？？ 
cnt:桶 
*/
il void ssa(string &s){//solve suffix array
    ri int i,to=s.size(),m=to>127?to:127,num;//m是rk的上界，受限于第一次要用ascII 
    s=' '+s;
    //处理单字符后缀 
    for(i=1;i<=to;++i) ++cnt[rk[i]=s[i]];//唯一一次的信息获取和朴素计数排序 
    for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];//前缀和。前缀和后，cnt[i]即为被丢到i处的最后一个元素的排名 
    for(i=to;i>=1;--i) sa[cnt[rk[i]]--]=i;//cnt[i]-原cnt[i]+1~cnt[i]恰为其排名

    for(ri int len=1;len<to;len<<=1){//当前处理的是长度为多少的后缀
        memset(cnt,0,sizeof(cnt));//先清空桶。(前缀和意义下的桶用完也不是空的) 
        for(i=1;i<=to;++i) ++cnt[rk[i + len]];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=to;i>=1;--i) sa[cnt[rk[i+len]]--]=i;

        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=to;++i) id[i]=sa[i];
        for(i=1;i<=to;++i) ++cnt[rk[id[i]]];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=to;i>=1;--i) sa[cnt[rk[id[i]]]--]=id[i];
        //这里用id而上面初始化用i，是要考虑它本身已有的顺序。
        //sa也即id的升序就是 sorted 的序，而rk是做不到这个的
        //第一关键字的排序是基于第二关键字的，从而必须基于上一次的序
        //也即上一次的sa。而rk只负责把它转回原字符串上找拼接
        //如果不基于上一次，那上次的排序结果就被忽略了
        //只有基于上一次的sa的顺序放入和取出，计数排序才是稳定的

        memcpy(oldrk,rk,sizeof(rk));
        for(num=0,i=1;i<=to;++i)
            if(oldrk[sa[i]]==oldrk[sa[i-1]] && oldrk[sa[i]+len]==oldrk[sa[i-1]+len])
                rk[sa[i]]=num;
            else 
                rk[sa[i]]=++num;
    }
}

• 但是，这份代码的常数之大，无法接受（甚至不比 stable\_sort 快）。所以，我们给它来几个常数优化。
  • 注意到，对第二关键字的计数排序好像并不那么必要：
    • 第二关键字对应串为空串的，我们很容易确定它应该在最前面。
    • 第二关键字不为空串的，应该上一轮被算过。可以考虑直接用。
  • 开辅助数组 px 存下常用的 rk[id[i]]。乍一看反而增大了常数，但事实上这样减少了不连续内存访问，对寄存器十分友好，能够大大提高命中率。
  • 用 cmp 函数代替原本算 rk 时很长的 if。类似上面这个，传值而非传参就可以减少不连续内存访问。
  • 若 num=n 则无需再排序。此时各个后缀“胜负已分”，rk 不重，每个排名都不同，没有必要继续排。

int sa[maxn],id[maxn],rk[maxn],oldrk[maxn],px[maxn],cnt[maxn];
bool cmp(int x,int y,int len){return oldrk[x]==oldrk[y] && oldrk[x+len]==oldrk[y+len];}
il void ssa(string &s){
    ri int i,to=s.size(),m=to>127?to:127,len,num;//m是rk的上界
    s=' '+s;

    for(i=1;i<=to;++i) ++cnt[rk[i]=s[i]];
    for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for(i=to;i>=1;--i) sa[cnt[rk[i]]--]=i;

    for(len=1;;len<<=1,m=num){
        for(num=0,i=to;i>to-len;--i) id[++num]=i;//i+w>n，即第二串为空 
        for(i=1;i<=to;++i) if(sa[i]>len) id[++num]=sa[i]-len;
        //当前串可以做第二串，则将串头按当前串排序放过去 
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=to;++i) ++cnt[px[i]=rk[id[i]]];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=to;i>=1;--i) sa[cnt[px[i]]--]=id[i];

        memcpy(oldrk,rk,sizeof(rk));
        for(num=0,i=1;i<=to;++i)
            rk[sa[i]]=cmp(sa[i],sa[i-1],len)?num:++num;

        if(num==to){
            for(i=1;i<=to;++i) sa[rk[i]]=i;
            break;
        }
    }
}

应用

• 一个显然的事实是，字符串的任意子串都是某个后缀的前缀。

• 在线求模式串在文本串中的出现。

  • 预处理文本串的后缀数组，就可以在 O(|p|\log |t|) 的时间内二分查找。
  • 具体来讲，在 sa 数组上二分。每次找到 sa_{now} 对应的后缀将其与模式串逐位比较（只比较 |p| 位），一个相同不跳，最终为 l-1，一个相同必跳，最终为 r。
  • 从而 sa_{l\sim r} 就是 |p| 在 |t| 中的所有出现。
  • 在 |t| 较大时，有着远优于 KMP/z 函数的表现，还有一个不同就是那些都依赖于预处理模式串，这个依赖于预处理文本串，对于多个模式串在单文本串的出现有更加优秀的表现。

• 把各种怪问题解决一下。

  • P4051 [JSOI2007]字符加密
  • 求原字符串的所有同质（首尾循环意义上）字符串按字典序排序后取出末尾字符构成的串。
    • 直接暴力拼接然后构造后缀数组，显然后面多拖一段对于各个后缀之间的字典序没有影响，从而算一下结尾点按 rk 放进去就好。
  • P2870 [USACO07DEC]Best Cow Line G
    • 可以从原串首尾拿字符，求构成的最小字典序串。
    • 显然当前位不同直接贪当前位，当前位相同就得有远见地贪了。
    • 从前往后拿相当于问后缀的字典序，从后往前拿相当于问前缀字典序，而且得把两者放到一块分出高低。
    • 直接把串翻转后和自己拼接一下，同上多拖一段没有影响（字典序中任意字符都大于空字符，或者说长的字典序大）。
    • 则就是对着 rk 做的裸的贪心。

• 扩展：height 数组

  • 定义 height_i=|\operatorname{lcp}(sorted_i,sorted_{i-1})|，其中 \operatorname{lcp} 为最长公共前缀（longest common perfix）。

    • 这个东西显然具有传递性，即 |\operatorname{lcp}(sorted_i,sorted_j)|=\min_{k=i+1}^j{height_k}。
    • 简单来说，就是因为这是按字典序排的，所以对于 sorted_i 来说，取 i<j<k，则有 |\operatorname{lcp}(sorted_i,sorted_j)|\geqslant |\operatorname{lcp}(sorted_i,sorted_k)|。当 k<j<i 时，结论是一样的。
    • 严谨证明比较繁琐，我们感性理解一下：按字典序排序后，从前面开始越多位和我一样（即 \operatorname{lcp} 越长）的后缀，和我在下标意义上离得越近。

  • 考虑怎么求 height。

    • 先放结论：height_{rk_i}\geqslant height_{rk_{i-1}}-1。

    • 为什么呢？我们放一张图感性理解一下。

    • 用自然语言讲出来，就是：

    • 首先，它们分别对应 |\operatorname{lcp}(sorted_{rk_i},sorted_{rk_i-1})| 和 |\operatorname{lcp}(sorted_{rk_{i-1}},sorted_{rk_{i-1}-1})|。

    • 其分别的前项，在原串上对应的前缀，是相邻的两个（s_i 和 s_{i-1}，注意 s_{i-1} 是较长的那个）。

    • 现在我们考察其后项。

    • 如果存在一个后项，使得 height_{rk_{i-1}}=k，那么有一个很显然的事情：存在另外一个地方的后缀，它的开头和 sorted_{rk_{i-1}} 长得一样。

    • 考虑把这个“另一个后缀”的开头和 sorted_{rk_{i-1}} 的第一个字母同时抛弃，显然，两者 \operatorname{lcp} 的剩余部分还是一样的，而“另一个后缀”抛弃开头后必然是“另另一个后缀”，同时 sorted_{rk_{i-1}} 抛弃开头就是 sorted_{rk_i}。

    • 即，两者分别抛弃一个字符就是新 height_{rk_i} 的下界。

    • 那简单了。最多抛弃 n 次，则总暴力匹配次数最多 2n，总复杂度为 O(n) 级别。

int hei[maxn];//注意下标是 sorted 的 
il void she(string &s){//solve height
    int to=s.size()-1;
    For(i,1,to){
        hei[rk[i]]=max(0,hei[rk[i-1]]-1);
        while(i+hei[rk[i]]<=to && sa[rk[i]-1]+hei[rk[i]]<=to && s[i+hei[rk[i]]]==s[sa[rk[i]-1]+hei[rk[i]]]) 
            ++hei[rk[i]];
        //去和 sorted[rk[i]-1]做匹配。它对应的是 sa[rk[i]-1] 开始的后缀。 
    }
}

• * 求本质不同子串个数（P2408 不同子串个数） * 每个 $height$ 都是不同后缀的相同前缀，$height$ 的值恰为其共同前缀长度，也即定死这个起点的重复数。 * 从而答案就是 $\dfrac{n(n+1)}{2}-\sum height$。 * 求子串的出现次数（P2852 [USACO06DEC]Milk Patterns G） * 因为 $sorted$ 的字典序是连续的，所以子串在 $sorted$ 中的各个后缀中的出现也必然是连续的。 * 从而找到它的首个出现位置 $sorted_i$ 然后往后极大化扩展直到有一个 $height_j\leqslant |sub|$，此时我们就找到了它的出现区间：$[i,j-1]$。 * 当然这个首个出现位置不好找，所以这个例题里面是卡住了出现次数问我们最长子串，则显然直接卡住出现区间的长度然后求 $\max (\min_i^{j-1} height)$。