Logo

菜单

后缀数组全家桶-从哈希乱搞到入门

wjyppm
发布于 2025-07-03 / 1 阅读
0
0
#字符串#笔记#题解

可能更好的阅读体验

0. 前言

后缀数组是信息学竞赛中解决字符串匹配的一大利器，其思想和实现非常简单。虽然倍增加排序的思想很简单，但是它的拓展 ht 数组功能及其强大并且适用性广，在 OI 范围内广泛应用。

以下应用魏老师的一句话：

几乎所有字符串算法都存在一个共性：基于所求信息的特殊性质与已经求出的信息，使用增量法与势能分析求得所有信息。这体现了动态规划思想。—— Alex_Wei

希望读者也能好好利用这句话来理解字符串算法。

本文章包含后缀数组入门，以及应用，以及技巧及其好题选讲大礼包！

但是作为本蒟蒻第一个写的算法全家桶，为了考虑到读者感受，写了一大堆没用的废话导致文章及其的长 ( •́ὤ•̀)，本文章共 2.1 万字，感谢管理员付出时间来进行审核。

一些基本约定：

  • 本文章默认字符串下表从 1 开始。
  • 我们用打字机字体表示字符串的内容，如：s=\texttt{wjyppm1403}。
  • 拼接：s+t 表示将 t 拼接 s 后。
  • 字符集：即构成字符串中字符的集合。
  • 空串：不含任何字符的字符串称为空串。
  • 子串：在 s 开头或末尾删去若干字符得到的字符串称作为 s 的子串，s 本身和空串也是 s 的子串。我们定义 s[l,r] 表示 l \to r 上所有字符链接而成子串。
  • 匹配：称 t 匹配 s 当且仅当 t 在 s 中出现。
  • 字符串长度：我们用 |s| 来表示 s 的长度。

前后缀：

  • 前缀：在 s 末尾删除若干字符得到的字符串称作 s 的前缀，记为 pre。
  • 后缀：在 s 开头删除若干字符得到的字符串称作 s 的后缀，记为 suf。
  • 最长公共前缀：\operatorname{LCP}(s,t)，表示 s,t 的最长公共前缀，即最长的 u 使得 u 为 s,t 的前缀。最长公共后缀同理，我们称为 \operatorname{LCS}(s,t)。LCP 的长度格式为：|\operatorname{LCP}(s,t)|。
  • 字典序：定义空字符小于任何字符。称 s 的 字典序 小于 t 当且仅当去掉 \operatorname{LCP}(s,t) 后，s 的第一个字符小于 t 的第一个字符。等价于以第 i 个字符作为第 i 关键字比较。

我们先从概念讲起。

1. 后缀树与后缀数组

1.1 朴素后缀树

一个字符串的后缀是指从某个位置开始到结尾的一个子串，即 suf_{i}=s[i \to len]。例如字符串 s=\texttt{"vamamadn"}，它的后缀有 8 个，suf_{0}=\texttt{"vamamadn"},suf_{1}=\texttt{"amamadn"},suf_{2}=\texttt{"mamadn"} 等。

而后缀树，就是把字符串所有后缀子串通过字典树的方法建立的一颗树。如下图：

我们对每一个后缀加上符号 表示一个后缀子串的末尾，用 是因为它不会出现字符串的字符集里面，适合用来做表示或分隔符。若要在字符串上找一个子串是否出现，如 \texttt{"mam"}，只需要在后缀树上查找就可以啦。

但是，问题在于，你全部显式的建出来那你空间不就炸掉了吗。我们思考这样的朴素后缀树的问题在哪里，这种方法的本质就是把一个长度为 n 的字符串拆成 n 个后缀子串，让后按照字典树来进行构造。但问题在于这样构建下来，每一次插入都是 O(n) 的时间复杂度，而遍历同样。并且当最坏情况下字符串字符互不相同的时候时间复杂度和空间复杂度都退化到 O(n^2)，一般情况下我们是无法接受的，那有没有什么好用的呢？

1.2 后缀数组

由于不方便直接对后缀树进行构造，我们利用后缀数组这种简单的方法来替代它，我们定义：sa_{i} 表示将所有后缀排序后第 i 小的后缀的位置。这也就是我们所说的后缀数组。

那么将上面后缀树的例子，我们用后缀数组来表示一下：

后缀 suf_i 下表 i 字典序 后缀数组 sa_j 下表 j
\texttt{"vamamadn"} 1 \texttt{"adn"} 6 1
\texttt{"amamadn"} 2 \texttt{"amadn"} 4 2
\texttt{"mamadn"} 3 \texttt{"amamadn"} 2 3
\texttt{"amadn"} 4 \texttt{"dn"} 7 4
\texttt{"madn"} 5 \texttt{"madn"} 5 5
\texttt{"adn"} 6 \texttt{"mamadn"} 3 6
\texttt{"dn"} 7 \texttt{"n"} 8 7
\texttt{"n"} 8 \texttt{"vamamadn"} 1 8

很明显，后缀数组的下表对应的就是后缀子串的字典顺序，记录的子串的有序排列。例如 sa_{1}=5 表示排名为 1（即字典序最小）的后缀是源字符串从第 5 个位置开始的后缀子串。

上面是一个例子，下面是 OI-Wiki 的例子：

我们定义另外一个数组 rk 表示 suf_{i} 在字符串所有后缀的字典序排名，我们称作排名数组。显然，rk 与 sa 是互为逆运算的：

  • sa：将排名映射到源字符串的位置。
  • rk：将位置映射到源字符串的字典序排名。

那么有 sa(rk[i])=i,rk(sa[i])=i。

那么现在问题在于如何给这些后缀通过排序求出排名。有一个显而易见的想法是从最后一位开始枚举后缀，然后每次存下当前枚举到的字符串，最后排序并输出就 OK 辣！

但是这样显然复杂度起步就是 O(n^2)，排序复杂度就能够达到恐怖的 O(n^2 \log n)，是无法接受的。

但是我们考虑，我们每一次都是一位一位比较的，我们能不能多位进行比较呢。这个时候我们就要用到倍增的思想：

首先对字符串 s 长度为 1 的子串，即每个字符进行排序，得到排序后的编号数组 sa_{i} 和排名数组 rk_{i}，如下 OI-Wiki 的图：

1751521949109.png

第二次，我们根据倍增向后移 2^0=1 位，因为已经根据首字母排了一次序，所以现在就根据后面的排序。我们让第一关键字设置为上一次我们求得的 rank，第二关键字设置为下一位的字符：

1751522031127.png

第三次，移 2^1=2 位，还是根据我们上面的思路，让第一关键字设置为上一次我们求得的 rank，第二关键字设置为下一位的字符：

1751522105354.png

唉？我们好像倍增完了，这样的话我们就求得了所有的 rank，接下来根据后缀数组性质：sa(rk[i])=i，就能够求出来 sa 啦。这样的时间复杂度，排序贡献 O(n \log n)，倍增贡献 O(\log n)，这样的时间复杂度就是 O(n \log^2 n)。

再看一遍整体的过程：

但是这样显然过不去我们可爱的 P3809，因为它要求 O(n\log n)，我们考虑刚才的做法，排序是 O(n \log n) 的，我们能不能从这里下手呢？我们可以考虑利用基数排序，这样我们就能做到 O(n) 啦，代码如下：

void getsa(){
    for(int i=1;i<=n;i++){
        x[i]=s[i];// x 就是
        c[x[i]]++; //桶排
    }
    for(int i=1;i<=m;i++){
        c[i]+=c[i-1];
        //做一个前缀和。这样字典序越大，所对应的的 c 越大。
    }
    for(int i=n;i>=1;i--){
        sa[c[x[i]]--]=i;
        //为何要减呢？若c[x[i]]>1表示有重复的，要保证排序不一样。
    }
    for(int len=1;len<=n;len<<=1){// 倍增
        int num=0;
        for(int i=n-len+1;i<=n;i++){
            y[++num]=i;
            //n-len+1已经排序完因为它们再倍增就倍增到空气啦。我们直接存在 y 中。
        }
        for(int i=1;i<=n;i++){
            if(sa[i]>len) y[++num]=sa[i]-len;
        // 若 i 可作其他位置的第二关键字，我们把他放在对应的第一关键字
        }
        for(int i=1;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--){
            sa[c[x[y[i]]]--]=y[i];
            y[i]=0;
            // 注意, 倒序枚举保证计数排序的稳定性. 基数排序的正确性基于内层计数排序的稳定性.
        }
        //和以前一样更新sa，但是排序是y[i]
        swap(x,y);
        num=1;
        x[sa[1]]=1;
        for(int i=2;i<=n;i++){
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len]) x[sa[i]]=num;
            else x[sa[i]]=++num;
        }
        //以上都是在更新 x
        if(num==n) break;// n 个排名互不相同, 排序完成.
        m=num;
    }
}

关于成熟的模板我们之后再说。对于上面的内容其实都比较还算简单，但是 SA 真正的神就在于 Height 数组，我们这里简称为 ht。

1.3 Height 数组

回顾 LCP 的定义：

最长公共前缀：\operatorname{LCP}(s,t)，表示 s,t 的最长公共前缀，即最长的 u 使得 u 为 s,t 的前缀。

而 Height 数组的定义就是：ht[i]=\operatorname{LCP}(sa[i],sa[i-1])，就是第 i 名的后缀与它前一名的后缀的最长公共前缀。特别的，我们记 ht[1]=0。

绝大多数 SA 的应用都需要 ht，很少见只用 sa,rk 就能解决的题目。不过分地说，后缀数组求 sa 就是为了求 ht。

那么怎么求？有一个朴素的想法就是哈希加二分，这个想必读者在做哈希题经常会见到这种操作。不然为什么我们标题叫哈希乱搞到入门，我们有一个结论：

若 rk_{i}<rk_{j}<rk_{k}，则 |\operatorname{LCP}(i,j)| 和 |\operatorname{LCP}(j,k)|，均不小于 |\operatorname{LCP}(i,k)|。

证明？设 t=|\operatorname{LCP}(i,k)|，因为 suf_{j} 的字典序在 suf_{i},suf_{k} 之间，所以 suf_{j} 的前 t 个字符必然与 suf_{i},suf_{k} 相等。这个还是比较容易理解的，因为字典序距离越近，LCP 越长吗。

若我们希望不要 O(n \log n) 的求 ht 的话，我们自然考虑其性质：

假设 ht_i 已知，则 |\operatorname{LCP}(sa_{i},sa_{i-1})|=ht_{i}。考虑 suf(sa_{i-1}+1),suf(sa_{i}+1)。当 ht_{i}>0，显然有 |\operatorname{LCP}(sa_{i}+1,sa_{i-1}+1)|=ht_{i}-1，且根据 rk(sa_{i-1})<rk(sa_{i})，容易证明 rk(sa_{i-1}+1)<rk(sa_{i}+1)。

令 p=sa_{i}+1,q=sa_{i-1}+1，我们尝试求出 rk_{p} 所对应的 ht，我们现在有如下性质：

  • |\operatorname{LCP}(p,q)|=ht_{i}-1。
  • rk(q)<rk(p)。

我们考虑，排名为 rk_{p}-1 的后缀 suf_r 的排名它要么等于 rk_q，那么 q=r。要么夹在 rk_q,rk_p 之间，因为 rk_r 是小于 rk_p 的最大正整数 rk_{p}-1，而 rk_q 小于 rk_p。那么根据上面结论，有 ht(rk_{p})\ge ht_{i}-1。我们考虑把 rk_{p} 换一下，有 ht(rk(sa_{i}+1))\ge ht(rk(sa_{i}))-1，那么令 u=sa_{i}+1，那么我们就有的 ht 数组的核心性质：

ht(rk_{u})\ge ht(rk_{u-1})-1

我们这里引用 Alex_Wei 的图：

1751524051020.png

通过这个性质，我们可以通过类似于双指针的性质来暴力求解 ht，以下为代码：

for(int i=1;i<=len;i++) rk[sa[i]]=i;
        for(int i=1,k=0;i<=len;i++){
            if(rk[i]==1) continue;
            if(k) k--;
            int j=sa[rk[i]-1];
            while(i+k<=len&&j+k<=len&&s[i+k]==s[j+k]) k++;
            ht[rk[i]]=ST[0][rk[i]]=k;
        }

下面是一个完整的模板，但是里面有一些函数还没有讲解，在应用中我们会逐个讲解：

namespace SA{
    int len,sa[MN],x[MN],y[MN],rk[MN],c[MN],ht[MN],ST[30][MN];

    // 接受 string 和 vector_int 输入，其他输入不保证正确性
    // ST表需要手动初始化调用initst函数
    template<typename vct>
    void getsa(vct &s){
        int m=400000;
        len=s.size();
        s.insert(s.begin(),' ');
        for(int i=1;i<=len;i++){
            x[i]=s[i];
            ++c[x[i]];
        }
        for(int i=2;i<=m;i++) c[i]+=c[i-1];
        for(int i=len;i>=1;i--) sa[c[x[i]]--]=i;
        for(int k=1;k<=len;k<<=1){
            int num=0;
            for(int i=len-k+1;i<=len;i++) y[++num]=i;
            for(int i=1;i<=len;i++){
                if(sa[i]>k) y[++num]=sa[i]-k;
            }
            for(int i=1;i<=m;i++) c[i]=0;
            for(int i=1;i<=len;i++) c[x[i]]++;
            for(int i=2;i<=m;i++) c[i]+=c[i-1];
            for(int i=len;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y);
            num=1,x[sa[1]]=1;
            for(int i=2;i<=len;i++){
                if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=num;
                else x[sa[i]]=++num;
            }
            if(num==len) break;
            m=num;
        }
        for(int i=1;i<=len;i++) rk[sa[i]]=i;
        for(int i=1,k=0;i<=len;i++){
            if(rk[i]==1) continue;
            if(k) k--;
            int j=sa[rk[i]-1];
            while(i+k<=len&&j+k<=len&&s[i+k]==s[j+k]) k++;
            ht[rk[i]]=ST[0][rk[i]]=k;
        }
    }

    // ST表初始化
    void initst(){
        for(int i=1;i<30;i++){
            for(int j=1;j+(1<<i)-1<=len;j++){
                ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
            }
        }
    }

    // 查询位置为 i 和 位置为 j 的后缀的 LCP
    int querylcp(int i,int j){
        if((i=rk[i])>(j=rk[j])) swap(i,j);
        int d=__lg(j-(i++));
        return min(ST[d][i],ST[d][j-(1<<d)+1]);
    }

    // 手动查询 ST 表
    int queryst(int l,int r){
        int d=__lg(r-l+1);
        return min(ST[d][l],ST[d][r-(1<<d)+1]);
    }

}

2. 后缀数组的应用

后缀数组有着许许多多的应用，但是由于对应的例题过于杂且用到的芝士较多，我们的顺序是先讲解技巧，先认识，让后我们在最后一部分的习题环节进行练习。有一些应用是对应少见的例题，所以这里会直接进行讲解而不会放在习题。

2.1 寻找最小的循环移动位置

循环移动位置实际上就是将字符串排为一个环，让后旋转这个环，我们先要断环成链将给定字符串复制一遍放在后面，这样就变为了后缀排序问题。

JSOI2007字符加密

我们发现，循环移动位置实际上就是将字符串排为一个环，让后旋转这个环，我们先要断环成链。把给定字符串复制一遍放在后面。让后你发现题目其实就是把这个改变后的字符串进行后缀排序，我们根据后缀排序的数组让后输出对应最后一位就可以了：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=8e5+15;
int x[MN],n,m,y[MN],c[MN],sa[MN];
string s;

void getsa(){
    for(int i=1;i<=n;i++){
        x[i]=s[i];
        c[x[i]]++;
    }
    for(int i=2;i<=m;i++){
        c[i]+=c[i-1];
    }
    for(int i=n;i>=1;i--){
        sa[c[x[i]]--]=i;
    }
    for(int len=1;len<=n;len<<=1){
        int num=0;
        for(int i=n-len+1;i<=n;i++){
            y[++num]=i;
        }
        for(int i=1;i<=n;i++){
            if(sa[i]>len){
                y[++num]=sa[i]-len;
            }
        }
        for(int i=1;i<=m;i++){
            c[i]=0;
        }
        for(int i=1;i<=n;i++){
            c[x[i]]++;
        }
        for(int i=2;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--){
            sa[c[x[y[i]]]--]=y[i];
            y[i]=0;
        }
        swap(x,y);
        num=1;
        x[sa[1]]=1;
        for(int i=2;i<=n;i++){
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len]){
                x[sa[i]]=num;
            }else x[sa[i]]=++num;
        }
    }
}


int main(){
    cin>>s;
    n=s.length()*2;
    m=300000;
    s=' '+s+s;
    getsa();
    for(int i=1;i<=n;i++){
        if(sa[i]<=n/2) cout<<s[sa[i]+n/2-1];
    }
    return 0;
}

2.2 在字符串中寻找最长公共子串

细节我给同学讲解 Trie 习题后教练考我这个问题，还好我即会后缀数组也会哈希做法 www。

同学问我哈希怎么做，显然最长公共子串的长度满足可二分性，考虑二分最长公共子串长度 L ，现在问题转化为判定性问题。我们考虑最简单的情况：两个串。我们对第一个串拿长度为 L 的滑块在上面滑，过程中把哈希值存下来到哈希表，第二个串同样，但我们判断哈希值是否出现过即可，这个情况可以拓展到一般串的情况，时间复杂度 O(n \log n) 但常数极大！这是一个滑块思想的应用。

如何用 SA 做呢？现在我们要求在主串 T 中寻找子串 S，我们先建出 T 的后缀数组，让后查找子串 S。若子串在 T 中出现，它必定是 T 的一些后缀的前缀，我们可以通过在后缀数组中二分 S 来实现。比较子串 S 和后缀的时间复杂度是 O(|S|) 的，那么总时间复杂度是 O(|S| \log |T|) 的，注意，如果该子串在 T 中出现了多次，每次出现都是在后缀数组数组中相邻的。因此出现次数可以通过再次二分找到，输出每次出现的位置也很轻松。

这一部分主要考察二分的操作使用，在下面的例题中我们也会详细的进行讲解。

2.3 从字符串首尾取字符最小化字典序

给你一个字符串，每次从首或尾取一个字符组成字符串，问所有能够组成的字符串中字典序最小的一个。

例题：「USACO07DEC」Best Cow Line。

一个暴力的想法就是 O(n) 判断取首还是取尾，我们现在只需要优化即可，因为取尾实际上就是在反串中取，我们可以将原串后缀和反串后缀构成的集合比较大小，可以将反串拼接在原串后，并在中间加上分隔符，求后缀数组，即可 O(1) 判断：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e6+15;
int x[MN],y[MN],rk[MN],sa[MN],c[MN],n,sn,m;
string s,revs;

void getsa(){
    for(int i=1;i<=n;i++){
        x[i]=s[i];
        c[x[i]]++;
    }
    for(int i=1;i<=m;i++){
        c[i]+=c[i-1];
    }
    for(int i=n;i>=1;i--){
        sa[c[x[i]]--]=i;
    }
    for(int len=1;len<=n;len<<=1){
        int num=0;
        for(int i=n-len+1;i<=n;i++){
            y[++num]=i;
        }
        for(int i=1;i<=n;i++){
            if(sa[i]>len){
                y[++num]=sa[i]-len;
            }
        }
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            c[x[i]]++;
        }
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--){
            sa[c[x[y[i]]]--]=y[i];
            y[i]=0;
        }
        swap(x,y);
        num=1;
        x[sa[1]]=1;
        for(int i=2;i<=n;i++){
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+len]==y[sa[i-1]+len]){
                x[sa[i]]=num;
            }else x[sa[i]]=++num;
        }
    }
    for(int i=1;i<=n;i++){
        rk[sa[i]]=i;
    }
}

int main(){
    cin>>n;
    m=5e5;
    for(int i=1;i<=n;i++){
        char awa;
        cin>>awa;
        s.push_back(awa);
    }
    for(int i=s.length()-1;i>=0;i--){
        revs.push_back(s[i]);
    }
    sn=n;
    // cout<<s<<'\n'<<revs<<'\n';
    s=' '+s+(char)0+revs;
    n=(n*2+1);
    getsa();
    int tot=0;
    for(int l=1,r=sn;l<=r;){
        if(rk[l]<rk[n+1-r]){
            cout<<s[l++];
        }else cout<<s[r--];
        if((++tot)%80==0) cout<<'\n';
    }
    return 0;
}

2.4 与贪心与 DP 的结合

对于后缀数组，在贪心和 DP 中一般不作为主角出现，多用于字符串加速匹配的问题或者利用其性质进行求解。

2.5 与线段树等一类数据结构结合

某些题目让你求满足条件的前若干个数，而这些数又在后缀排序中的一个区间内。这时我们可以用归并排序的性质来合并两个结点的信息，利用线段树维护和查询区间答案。

同时后缀数组会根据题目的不同结合一系列数据结构算法，如莫队，扫描线等。在习题部分我们会单独开讲。

3. Height 数组的应用

3.1 任意两个后缀的 LCP

有了 ht 数组，我们可以快速求出一个字符串 s 的 i 后缀和 j 后缀的最长公共前缀 \operatorname{LCP}(i,j)。

结论如下：

若 rk_{i}<rk_{j}，则 |\operatorname{LCP}(i,j)|=\min\limits_{p=rk_{i}+1}^{rk_{j}}ht_p。

感性理解以下，如果 Height 一直大于某个数，前这么多位就一直没变过；反之，由于后缀已经排好序了，不可能变了之后变回来。

严格证明可以参考[2004] 后缀数组 by. 许智磊。那么通过这样，求两子串最长公共前缀就转化为了 RMQ 问题，这也就是对应了我们模板中的 ST 表，实现如下：

// ST表初始化
    void initst(){
        for(int i=1;i<30;i++){
            for(int j=1;j+(1<<i)-1<=len;j++){
                ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
            }
        }
    }

    // 查询位置为 i 和 位置为 j 的后缀的 LCP
    int querylcp(int i,int j){
        if((i=rk[i])>(j=rk[j])) swap(i,j);
        int d=__lg(j-(i++));
        return min(ST[d][i],ST[d][j-(1<<d)+1]);
    }

我们这里引用 Alex_wei 的图：

1751526880179.png

上图就是对 \texttt{aabaaaab} 进行后缀排序后的结果以及 ht 数组，由矩形框起来的两个字符串相等。那么根据上面的图也能理解两个后缀之间的 LCP 就是它们排名之间所有矩形宽度的最小值，即 ht 的最小值。

但是，如果我们将整张图逆着旋转 90 的话，那么有：

1751527072274.png

我们得到了一个矩形柱状图！ht 恰好表示了每个矩形的高度，这也可能就说明了为什么名字叫做 Height 数组。观察这个图你有没有想到什么？

没错，这个玩意我们还是可以和单调栈结合起来一起考的！众所周知，单调栈可以求出柱状图中面积最大的矩形。

例如我们求所有后缀两两 LCP 长度之和，考虑按排名顺序加入所有后缀并实时维护 F(i)=\sum\limits_{p=1}^{i-1}|\operatorname{LCP}(sa_{p},sa_{i})|，那么其实就是在维护 \sum\limits_{p=1}^{i-1} \min\limits_{q=p+1}^{i} ht_{q}，可以视为把单调栈加入高 ht_{i}，宽 1 的矩形后，单调栈内矩形面积之和。

3.2 求本质不同子串数

可以用 s 所有后缀的前缀表示所有子串，我们考虑每次添加一个后缀，并删去这个后缀与已经添加的后缀的所有重复前缀，而前缀总数就是子串个数，为 \dfrac{n(n+1)}{2}，如果按后缀排序的顺序枚举后缀，每次新增的子串就是除了与上一个后缀的 LCP 剩下的前缀。这些前缀一定是新增的，否则会破坏 |\operatorname{LCP}(i,j)|=\min\limits_{p=rk_{i}+1}^{rk_{j}}ht_p 的性质。只有这些前缀是新增的，因为 LCP 部分在枚举上一个前缀时计算过了。那么答案就是 \dfrac{n(n+1)}{2}-\sum\limits_{i=2}^n ht_{i}。

上面的做法我们求得了 s 所有后缀本质不同的前缀数量。我们可以拓展到求 s 某个后缀集合 S 所有本质不同前缀数量！

设 S 的所有位置按排名从小到大排名后的位置分别为 p_1,p_2,\dots,p_{|S|}，答案就是：

\left( \sum\limits_{i=1}^{|S|} n-p_{i}+1 \right)-\left(\sum\limits_{i=1}^{|S|-1} |\operatorname{LCP}(p_{i},p_{i+1})| \right)

其中后面能够 ST 表预处理后 O(|S|) 求出。

3.3 多个串的最长公共子串

给出 n 个字符串，求 s_{1},s_{2},\dots,s_{n} 的最长公共子串。

首先我们先把这个字符串给拼接起来，格式入 t=s_{1}+c_{1}+s_{2}+c_{2}+\dots +c_{n-1}+s_{n}，其中 c_{i}=\texttt{'z'}+i，即分隔符，但要求互不相同不然就会出现影响答案的情况啦。

让后我们对 t 建出 SA 数组，问题转化为求 \max\limits_{1\le l \le r \le |t|} \min_{p=l+1}^r |\operatorname{LCP}(p,p-1)|，其中这个区间 [l,r] 合法当且仅当对于每一个字符串 s_i 的后缀都落在这个区间内。

容易发现 l 增大的时候 r 是单调不降的，我们可以考虑双指针维护整个过程。此外，我们还需要维护区间最小值，可以考虑利用单调队列就可以维护啦，时间复杂度 O(n+n \log n)。

3.4 结合并查集

某些题目求解时要求你将后缀数组划分成若干个连续 LCP 长度大于等于某一值的段，我们可以考虑根据 ht 的性质，当我们给定一个长度阀值 L 的时候，我们把所有 <L 的 ht 去掉，让后 ht 将区间划分为若干个子区间，同一子区间任意两个后缀的 LCP 长度均大于 L。将询问离线，我们从大到小考虑所有 ht_{i}，每次在 sa_{i-1},sa_{i}，之间连边利用数据结构如并查集加启发式合并维护这一过程，就可以得到每个后缀的 LCP 长度 \ge L 所有后缀的信息。

对 ht_{i} 建立笛卡尔树的效果是同样的。

3.5 连续的若干个相同子串

如果题目中出现一些构造字符串循环构成的问题，我们可以不妨考虑枚举这个循环的长度 L，让后按照 L 将字符串划分关键点分块（即按照 L 的倍数分块）利用分块和字符串的重复性质，将看似全局的问题局部化解决。对应到后缀数组上就是对相邻两块的块进行 LCP 和 LCS 查询，具体如何操作我们下面会讲解。

4. 例题

4.1 并查集技巧

P2852 [USACO06DEC] Milk Patterns G

呃其实就是板子题，这个真没有什么好说的，考虑从从大到小添加每个 ht_{i}，等价于每次在 sa_{i-1},sa_{i}之间连边，当出现大小为 k 的联通块时 ht_{i} 即为所求。如果你非要说 Oi-Wiki 的做法的话也是可以的吧……

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,k;
string a;
multiset<int> tt;

namespace SA{
// 省略
}using namespace SA;

int main(){
    cin>>n>>k;
    k--;
    for(int i=1;i<=n;i++){
        int c;
        cin>>c;
        a.push_back(c);
    }
    getsa(a);
    int ans=0;
    for(int i=1;i<=n;i++){
        tt.insert(ht[i]);
        if(i>k) tt.erase(tt.find(ht[i-k]));
        ans=max(ans,*tt.begin());
    }
    cout<<ans;
    return 0;
}

P2178 [NOI2015] 品酒大会

若 r 相似成立，那么对于 r'(1\le r' < r) 相似也是成立的。若我们考虑 \ge L 的 ht_{i}，将 sa_{i-1},sa_{i} 之间连边，若 p,q 在一个联通块，那么根据我们上面所说的，则 p,q 是 L 相似的。

我们考虑从大到小处理 ht_{i}，使用并查集与启发式合并维护每个联通块的大小以及所有权值，用最大值乘次大值，最小值乘次小值（有负数）更新当前合并后 L 的答案，时间复杂度为 O(n \log^2 n)，当然我们可以只维护最大，次大，最小，次小，这样就能做到 O(n \log n) 啦。其实这才是我们并查集技巧的题。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int MN=6e5+15;
int n,m,x[MN],y[MN],cnt[MN],pre[MN],sa[MN],rk[MN],h[MN],pos[MN];
ll mx[MN],mn[MN],ans1[MN],ans2[MN],ans[MN],a[MN],siz[MN];
string s;

namespace SA{
// 省略
}using namespace SA;

void geth(){
    for(int i=1,k=0;i<=n;i++){
        if(!rk[i]) continue;
        if(k) k--;
        while(s[i+k]==s[sa[rk[i]-1]+k]) k++;
        h[rk[i]]=k;
    }
}

void init(){
    memset(ans2,128,sizeof(ans2));
    for(int i=1;i<=n;i++){
        pre[i]=i;
        pos[i]=i;
        mx[i]=mn[i]=a[i];
        ans[i]=-1e18;
        siz[i]=1;
    }
}

int root(int x){
    if(pre[x]==x) return pre[x];
    else return pre[x]=root(pre[x]);
}

void merge(int x,int y,int len){
    x=root(x),y=root(y);
    pre[y]=x;
    ans1[len]+=(ll)siz[x]*siz[y];
    siz[x]+=siz[y];
    ans[x]=max({ans[x],ans[y],mx[x]*mx[y],mx[x]*mn[y],mn[x]*mx[y],mn[x]*mn[y]});
    mx[x]=max(mx[x],mx[y]);
    mn[x]=min(mn[x],mn[y]);
    ans2[len]=max(ans2[len],ans[x]);
}

bool cmp(int x,int y){
    return h[x]>h[y];
}

int main(){
    cin>>n;
    m=3e5;
    cin>>s;
    s=' '+s;
    for(int i=1;i<=n;i++) cin>>a[i];
    getsa();
    geth();
    init();
    sort(pos+2,pos+1+n,cmp);
    // for(int i=1;i<=n+1;i++){
    //     cout<<sa[i]<<" ";
    // }
    // cout<<'\n';
    for(int i=2;i<=n;i++){
        merge(sa[pos[i]],sa[pos[i]-1],h[pos[i]]);
    }
    for(int i=n;i>=0;i--) ans1[i]+=ans1[i+1];
    for(int i=n;i>=0;i--) ans2[i]=max(ans2[i],ans2[i+1]);
    for(int i=0;i<n;i++){
        cout<<ans1[i]<<" "<<(ans1[i]?ans2[i]:0)<<'\n';
    }
    return 0;
}

P6793 [SNOI2020] 字符串

我们考虑，每一次修改修改的都是一段后缀，启发我们对 a+b 拼接后形成的字符串进行后缀数组操作。我们有一个贪心的想法，我们每次修改两个 LCP 尽量长的子串，这个贪心显然正确的，证明考虑反证法即可。

那么，我们利用上面的思路，从大到小将 ht_{i} 插入，实质上就是在从大到小枚举 LCP 进行贪心，每次贪心的消除当前联通块尽可能多的 a,b 后缀对，时间复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
int n,ans,K,as[MN],bs[MN],pre[MN];
string a,b,s;
vector<int> pos[MN];

namespace SA{
	// 省略

}using namespace SA;

int root(int x){
    if(pre[x]==x) return pre[x];
    else return pre[x]=root(pre[x]);
}

void merge(int x,int y,int lcpl){
    int rx=root(x),ry=root(y);
    if(rx==ry) return;
    int tmp=min(as[rx],bs[ry]);
    ans+=max(0ll,K-lcpl)*tmp;
    as[rx]-=tmp;
    bs[ry]-=tmp;
    tmp=min(bs[rx],as[ry]);
    ans+=max(0ll,K-lcpl)*tmp;
    bs[rx]-=tmp;
    as[ry]-=tmp;
    as[ry]=as[rx]+as[ry],bs[ry]=bs[rx]+bs[ry];
    pre[rx]=ry;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>K>>a>>b;
    s=a+'#'+b;
    for(int i=1;i<=n;i++){
        as[i]=(i+K-1<=n);
    }
    for(int i=n+2;i<=2*n+1;i++){
        bs[i]=(i-n-1+K-1<=n);
    }
    for(int i=0;i<=2*n+1;i++){
        pre[i]=i;
    }
    getsa(s);
    initst();
    for(int i=n;i>=0;i--){
        for(auto p:pos[i]){
            merge(sa[p],sa[p-1],i);
        }
    }
    put(ans);
    return 0;
}

P7361 「JZOI-1」拜神

形式化题面如下：

给定一个长为 n 的字符串，询问次数为 q，多次询问区间 [l,r] 内最长重复子串的长度。

1\le n \le 5\times 10^4,1\le q \le 10^5。

没有形式化题面感觉都想不出来怎么做 www。

肯定没有那么菜啦，首先考虑二分长度，问题转化为区间内是否存在一个长为 mid 的最长重复子串。

接下来我们考虑这个最长重复子串怎么求，一个比较明显的想法就是后缀数组的 LCP 功能，原命题询问的实质就问是否存在 i,j \in [l,r-mid+1],\operatorname{LCP}(i,j)\ge mid。看到后面这个式子，回忆起品酒大会的思路：从大到小将 Height 数组插入，若仅考虑 \ge L 的 Height，将 sa_{i-1},sa_{i} 之间连边，那么若 p,q 在同一联通块里，表明 \operatorname{LCP}(p,q)\ge L。我们通过并查集和启发式合并就可以做到 O(\log n) 的优秀复杂度啦。

但是有点问题啊，如果我们直接这么做我们并没有考虑区间位置，也就是说在两个联通块启发式合并的时候我们必须要记录区间的位置。我们不妨考虑对于联通块内每一个位置，我们维护它在当前联通块内上一个元素的位置，记作 pre_{i}，那么区间限制转化为 \max\limits_{i\in set(L),i\in [l,r-L+1]} pre_{i}\ge l。我们可以通过对每一个联通块开主席树来辅助查询，这样就能够做到优秀的 O(q \log^2 n) 的查询啦，其中两个 \log 由二分和主席树查询贡献。

问题转化为如何维护 pre 的合并。首先，唯一确定一个联通块的信息就是所对应的 LCP 长度 L（具体见上面品酒大会思路），根据品酒大会启发式合并的思路，一次启发式 pre 的变化最多只有 O(\log n) 个，考虑用 set 把联通块内的元素存下来，启发式合并的时候暴力单点修改 pre，这样处理的复杂度是 O(n \log^2 n) 的，可以过。故总时间复杂度为 O(q\log^2 n + n \log^2 n)。

请注意二分的实现：

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
constexpr int MN=5e4+15;
int n,q,pre[MN];
vector<int> vht[MN];
set<int> st[MN];
string s;

struct Segment{
#define ls t[p].lson
#define rs t[p].rson

    struct Node{
        int lson,rson,val;
    }t[MN<<9];
    int tot,rt[MN];
    
    void pushup(int p){
        t[p].val=max(t[ls].val,t[rs].val);
    }

    void modfiy(int &p,int lst,int l,int r,int pos,int v){
        p=++tot;
        t[p]=t[lst];
        if(l==r){
            t[p].val=max(t[p].val,v);
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=pos) modfiy(ls,t[lst].lson,l,mid,pos,v);
        else modfiy(rs,t[lst].rson,mid+1,r,pos,v);
        pushup(p);
    }

    int query(int p,int l,int r,int fl,int fr){
        if(l>=fl&&r<=fr){
            return t[p].val;
        }
        int mid=(l+r)>>1,ret=0;
        if(mid>=fl) ret=max(ret,query(ls,l,mid,fl,fr));
        if(mid<fr) ret=max(ret,query(rs,mid+1,r,fl,fr));
        return ret;
    }

#undef ls
#undef rs
}sg;

namespace SA{
// 省略
}using namespace SA;

int root(int x){
    if(pre[x]==x) return pre[x];
    else return pre[x]=root(pre[x]);
  // 这里用这种合并方式而不是按秩合并
  // 是因为并查集维护的是联通块所属的集合，不用考虑形态变化。
}

void merge(int x,int y,int L){
    int rx=root(x),ry=root(y);
    if(rx==ry) return;
    if(st[rx].size()<st[ry].size()) swap(rx,ry);
    pre[ry]=rx;
    for(auto p:st[ry]){
        auto it=st[rx].lower_bound(p);
        if(it!=st[rx].end()){
            sg.modfiy(sg.rt[L],sg.rt[L],1,n,*it,p);
        }
        if(it!=st[rx].begin()){
            it--;
            sg.modfiy(sg.rt[L],sg.rt[L],1,n,p,*it);
        }
    }
    for(auto p:st[ry]) st[rx].insert(p);
}

int main(){
    cin>>n>>q>>s;
    getsa(s);
    for(int i=2;i<=n;i++){
        vht[ht[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        pre[i]=i;
        st[i].insert(i);
    }
    for(int i=n;i>=1;i--){
        sg.rt[i]=sg.rt[i+1];
        for(auto p:vht[i]){
            merge(sa[p],sa[p-1],i);
        }
    }
    while(q--){
        int L,R;
        cin>>L>>R;
        int l=0,r=R-L+1;
        while(l+1<r){
            int mid=(l+r)>>1;
            if(sg.query(sg.rt[mid],1,n,L,R-mid+1)>=L){
                l=mid;
            }else r=mid;
        }
        cout<<l<<'\n';
    }
    return 0;
}

4.2 单调栈技巧

P4248 [AHOI2013] 差异

前面两个都好说，关键字与后面这个每一个区间 LCP 之和怎么求回顾我们后缀数组求解 LCP 的式子：

若 rk_{i}<rk_{j}，则 |\operatorname{LCP}(i,j)|=\min\limits_{p=rk_{i}+1}^{rk_{j}}ht_p。

那么现在问题转化为求每个区间的区间最小值之和，我们利用单调栈，考虑按排名顺序加入所有后缀并实时维护 F(i)=\sum\limits_{p=1}^{i-1}|\operatorname{LCP}(sa_{p},sa_{i})|，那么其实就是在维护 \sum\limits_{p=1}^{i-1} \min\limits_{q=p+1}^{i} ht_{q}，可以视为把单调栈加入高 ht_{i}，宽 1 的矩形后，单调栈内矩形面积之和。后面的答案就是 \dfrac{n(n+1)(n-1)}{2}-2\times F(i)：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+51;
int top,sta[MN],L[MN],R[MN],ans;
string s;

namespace SA{
// 省略
}using namespace SA;

signed main(){
    cin>>s;
    getsa(s);
    sta[top=1]=1;
    for(int i=2;i<=len;i++){
        while(top&&ht[sta[top]]>ht[i]) R[sta[top--]]=i;
        L[i]=sta[top];
        sta[++top]=i;
    }
    while(top) R[sta[top--]]=len+1;
    ans=len*(len-1)*(len+1)/2;
    for(int i=2;i<=len;i++){
        ans-=2*(R[i]-i)*(i-L[i])*ht[i];
    }
    cout<<ans;
    return 0;
}

P7409 SvT

问题即求：

\sum_{i=1}^{K} \sum_{j=i+1}^{K} \operatorname{LCP}\left(suf_{i}, suf_{j}\right)

其中 K 为后缀集合长度，显然有：

\sum_{i=1}^{K} \sum_{j=i+1}^{K} \operatorname{LCP}\left(s_{i}, s_{j}\right)=\sum_{i=1}^{K} \sum_{j=i+1}^{K} \min _{r_{i}+1 \leq k \leq r_{j}}\left\{\text { ht}_{k}\right\}

直接单调栈做就可以了，但是记得要去重哦，因为给出的有重复的。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int MN=1e6+15;
constexpr ll MOD=23333333333333333;
int n,m,sta[MN],top,a[MN],w[MN],L[MN],R[MN];

namespace SA{

// 省略


    int lcp(int i,int j){
        if((i=rk[i])>(j=rk[j])) swap(i,j);
        int d=__lg(j-(i++));
        return min(st[d][i],st[d][j-(1<<d)+1]);
    }

}using namespace SA;

bool cmp(int x,int y){
    return rk[x]<rk[y];
}

int main(){
    string s;
    cin>>n>>m>>s;
    getsa(s);
    initst();
    while(m--){
        int t;
        ll ans=0;
        cin>>t;
        for(int i=1;i<=t;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+t);
        t=unique(a+1,a+1+t)-a-1;
        sort(a+1,a+1+t,cmp);
        w[1]=0;
        for(int i=2;i<=t;i++){
            w[i]=lcp(a[i-1],a[i]);
        }
        sta[top=0]=0;
        for(int i=1;i<=t;i++){
            while(top&&w[sta[top]]>w[i]) top--;
            L[i]=sta[top];
            sta[++top]=i;
        }
        sta[top=0]=t+1;
        for(int i=t;i>=1;i--){
            while(top&&w[sta[top]]>=w[i]) top--;
            R[i]=sta[top];
            sta[++top]=i;
        }
        for(int i=2;i<=t;i++){
            ans=(ans+1ll*w[i]*(R[i]-i)%MOD*(i-L[i])%MOD)%MOD;
        }
        cout<<ans<<'\n';
    }

    return 0;
}

P5161 WD 与数列

做这个题之前请先解锁：关键点 Trick。

一个序列整体加一个数后与另一个序列相同，其实就是差分数组相同，原因自行思考。

那么源问题去掉限制就是裸的单调栈，但是问题在于要求不相交的，我们可以考虑容斥，总方案数减去相交的方案。总方案单调栈做，问题在于相交如何求解？

但是若求不相交的两个区间信息，请注意在差分数组上求时应当是相隔一个位置。差分数组中相交或相邻的串在原串中都是相交的。

我们考虑相交怎么做，我们可以考虑枚举长度 k，每隔一个 k 放一个关键点的套路。这里我们枚举两个字符串偏移的距离，若一个字符串的开头位置为 p，那么第二个串的开头为 p+k，第一个串的结束位置必须要满足 q\ge p+k-1，发现 p 每次向右移动，q 的取值减小 1，等差数列求解即可。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e6+15;
int n,ans,a[MN],b[MN],top,tot;
pir st[MN];

struct SA{
// 省略。。。
}A,B;

int clac(int x,int y){
    return (x+y)*(y-x+1)/2;
}

signed main(){
    vector<int> s,t;
    cin>>n;
    --n;
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i>=1;i--){
        a[i]-=a[i-1];
        b[++tot]=a[i];
    }
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
        s.push_back(a[i]);
        t.push_back(a[i]);
    }
    A.getsa(s);
    reverse(t.begin(),t.end());
    B.getsa(t);
    A.initst();
    B.initst();
    int sum=0;
    for(int i=n;i>=1;i--){
        ans+=sum;
        int now=1;
        while(top&&st[top].first>=A.ht[i]){
            sum-=st[top].first*st[top].second;
            now+=st[top--].second;
        }
        st[++top]=pir(A.ht[i],now);
        sum+=now*A.ht[i];
    }
    for(int k=1;k<n;k++){
        for(int i=1;i<=n/k-1;i++){
            int x1=i*k,y1=x1+k,x2=n-y1+2,y2=n-x1+2;
            int lcs=min(k-1,B.querylcp(x2,y2)),lcp=A.querylcp(x1,y1);
            if(lcs+lcp-k+1<0) continue;
            ans-=clac(max(lcp-k+1,0ll),lcs+lcp-k+1);
        }
    }
    cout<<ans+n*(n+1)/2;

    return 0;
}

P5115 Check, Check, Check one two!

练习

CF1073G

[HAOI2016]找相同字符

4.3 SA加速匹配和查询子串

P3763 [TJOI2017] DNA

由于不重合的字符很少，考虑暴力枚举不重合的子串起始位置，让后从这个位置往后跳最长公共前缀的长度，这样如果枚举的位置正确也能保证后续位置也能递推正确。现在问题转化为如何快速求解 LCP，用二分加哈希或 SA 加 ST 表即可实现。

二分加哈希：

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
constexpr ull base=13131;
constexpr int MN=1e5+15;
int lena,lenb;
ull a[MN],b[MN],pw[MN];
string sa,sb;

void init(){
    pw[0]=1;
    for(int i=1;i<MN;i++) pw[i]=pw[i-1]*base;
}

ull hsha(int l,int r){
    return a[r]-a[l-1]*pw[r-l+1];
}

ull hshb(int l,int r){
    return b[r]-b[l-1]*pw[r-l+1];
}

bool binfind(int x){
    int st=1,r=x+lenb-1,ed=lenb;
    for(int i=1;i<=3;i++){
        int lt=-1,rt=ed-st+2,ret=0;
        while(lt+1<rt){
            int mid=(lt+rt)>>1;
            if(hsha(x,x+mid-1)==hshb(st,st+mid-1)) lt=mid;
            else rt=mid;
        }
        x+=lt+1;
        st+=lt+1;
        if(st>ed) return 1;
    }
    return hsha(x,x+lenb-st)==hshb(st,ed);
}

void solve(){
    cin>>sa>>sb;
    lena=sa.length(),lenb=sb.length();
    if(lena<lenb){
        cout<<0<<'\n';
        return;
    }
    sa=" "+sa;
    sb=" "+sb;
    for(int i=1;i<=lena;i++){
        a[i]=a[i-1]*base+sa[i];
    }
    for(int i=1;i<=lenb;i++){
        b[i]=b[i-1]*base+sb[i];
    }
    int ans=0;
    for(int i=1;i<=lena-lenb+1;i++){
        if(binfind(i)) ans++;
    }
    cout<<ans<<'\n';
}

int main(){
    init();
    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

SA：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,m;
string s,t;

namespace SA{

// 省略


    int lcp(int i,int j){
        if((i=rk[i])>(j=rk[j])) swap(i,j);
        int d=__lg(j-(i++));
        return min(st[d][i],st[d][j-(1<<d)+1]);
    }

}using namespace SA;

void solve(){
    cin>>s>>t;
    n=s.length(),m=t.length();
    s=" "+s,t=" "+t;
    string sst;
    for(int i=1;i<=n;i++){
        sst.push_back(s[i]);
    }
    sst.push_back('#');
    for(int i=1;i<=m;i++){
        sst.push_back(t[i]);
    }
    getsa(sst);
    initst();
    int ret=0;
    for(int i=1;i<=n-m+1;i++){
        int curs=i,curt=1;
        for(int j=1;j<=4;j++){
            if(curt<=m){
                int lcpl=lcp(curs,curt+n+1);
                curs+=lcpl+(j<4);
                curt+=lcpl+(j<4);
            }
        }
        ret+=curt>m;
    }
    cout<<ret<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

SP1812 LCS2

2.2 有讲两种做法。

现在我们要求在主串 T 中寻找子串 S，我们先建出 T 的后缀数组，让后查找子串 S。若子串在 T 中出现，它必定是 T 的一些后缀的前缀，我们可以通过在后缀数组中二分 S 来实现。比较子串 S 和后缀的时间复杂度是 O(|S|) 的，那么总时间复杂度是 O(|S| \log |T|) 的，注意，如果该子串在 T 中出现了多次，每次出现都是在后缀数组数组中相邻的。因此出现次数可以通过再次二分找到，输出每次出现的位置也很轻松。以下是 SA 的实现：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=3e6+15;
int col[MN],vis[MN],L[MN],R[MN],sum,tot,ans;
string s,str;
deque<int> q;

namespace SA{
// 省略

}using namespace SA;

void add(int x){
    if(col[x]==0) return;
    vis[col[x]]++;
    if(vis[col[x]]==1) sum++;
}

void del(int x){
    if(col[x]==0) return;
    vis[col[x]]--;
    if(vis[col[x]]==0) sum--;
}

int main(){
    while(cin>>s){
        tot++;
        L[tot]=str.length()+1;
        str=str+s;
        R[tot]=str.length();
        str.push_back(tot);
    }
    getsa(str);
    for(int i=1;i<=tot;i++){
        for(int j=L[i];j<=R[i];j++){
            col[rk[j]]=i;
        }
    }
    add(1);
    for(int r=2,l=1;r<=len;r++){
        while(!q.empty()&&ht[q.back()]>=ht[r]) q.pop_back();
        q.push_back(r);
        add(r);
        if(sum==tot){
            while(tot==sum&&l<r) del(l++);
            add(--l);
        }
        while(!q.empty()&&q.front()<=l) q.pop_front();
        if(tot==sum) ans=max(ans,ht[q.front()]);
    }
    cout<<ans;
    return 0;
}

P5028 Annihilate

把字符串加分隔符连接在一起，让后跑后缀数组求 ht，原本命题我们可以直接建立 st 秒了，但是空间炸缸了。但是时间复杂度启示我们 O(nm)？

考虑计算 LCP 的过程就是一段 ht 求最小值的过程，考虑贪心，越近越优，每一个不同的字符串只需要保存目前 ht 的最小值即可，这个值即是最近也是最小值中最大的。

放这个题就是为了看见 SA 不要僵化思路，这种一般是学多做题多了导致的 www。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=3e6+15,MK=55;
int n,pos[MN],minn[MK],ans[MK][MK];
vector<int> str;

namespace SA{
// 省略

}using namespace SA;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(auto c:s){
            str.push_back(c);
            pos[str.size()]=i;
        }
        str.push_back(1000+i);
    }
    getsa(str);
    for(int i=2;i<=len;i++){
        for(int j=1;j<=n;j++) minn[j]=min(minn[j],ht[i]);
        minn[pos[sa[i-1]]]=ht[i];
        for(int j=1;j<=n;j++){
            ans[pos[sa[i]]][j]=ans[j][pos[sa[i]]]=max(ans[pos[sa[i]]][j],minn[j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j) cout<<ans[i][j]<<" ";
        }
        cout<<'\n';
    }
    return 0;
}

P2463 [SDOI2008] Sandy 的卡片

一个序列整体加一个数后与另一个序列相同，其实就是差分数组相同，原因自行思考。

但是若求不相交的两个区间信息，请注意在差分数组上求时应当是相隔一个位置。差分数组中相交或相邻的串在原串中都是相交的。

那么先求差分数组，让后两个差分数组中间加分隔符连起来建立 SA，让后问题转化为求所有子串最长公共子串，考虑二分，只要有 n 个 \ge L 的 ht 并且这几个都属于不同的串就可以啦。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,lenn[MN],sta[MN],top,a[1145][1145];
int pos[MN];
bool vis[MN];
string s;

namespace SA{
 // 省略

}using namespace SA;

bool check(int x){
    while(top) vis[sta[top--]]=0;
    for(int i=1;i<=len;i++){
        if(ht[i]<x) while(top) vis[sta[top--]]=0;
        if(!vis[pos[sa[i]]]){
            vis[pos[sa[i]]]=1;
            sta[++top]=pos[sa[i]];
            if(top==n) return 1;
        }
    }
    return 0;
}

int main(){
    cin>>n;
    int l=0,r=1e6,ans=0;
    for(int i=1;i<=n;i++){
        cin>>lenn[i];
        for(int j=1;j<=lenn[i];j++){
            cin>>a[i][j];
        }
        r=min(r,lenn[i]-1);
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=lenn[i];j++){
            s.push_back(a[i][j]-a[i][j-1]);
            pos[s.length()]=i;
        }
        s.push_back('#');
    }
    getsa(s);
    
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else r=mid-1;
    }
    cout<<ans+1;
    return 0;
}

SP220 PHRASES - Relevant Phrases of Annihilation

划分为 2 个子问题：

  • 最长公共子串。
  • 最长且不重叠出现两次及以上的子串。

第一问我们不说，我们考虑第二问如何求解，我们可以对于 ht 分组，求除在原串中最大坐标和最小左边，判断差值是否大于 len 即可。

结合起来就可以啦，时间复杂度 O(S \log S)，其中 S=\sum\limits|s_{i}|。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e6+15;
int n,L[MN],R[MN];
string s;
vector<int> vct;

namespace SA{

    void clear(){
        memset(sa,0,sizeof(sa));
        memset(rk,0,sizeof(rk));
        memset(ork,0,sizeof(ork));
        memset(buc,0,sizeof(buc));
        memset(id,0,sizeof(id));
        memset(ht,0,sizeof(ht));
        memset(st,0,sizeof(st));
    }
// 省略
}using namespace SA;

bool check(int x){
    vct.clear();
    for(int i=1;i<=len;i++){
        if(ht[i]<x){
            bool flag=true;
            for(int j=1;j<=n;j++){
                int mn=MN,mx=0;
                for(int p:vct){
                    if(p<L[j]||p>R[j]) continue;
                    mn=min(mn,p);
                    mx=max(mx,p);
                }
                if(mx-mn<x){
                    flag=false;
                    break;
                }
            }
            if(flag) return true;
            vct.clear();
        }
        vct.push_back(sa[i]);
    }
    bool flag=true;
    for(int j=1;j<=n;j++){
        int mn=MN,mx=0;
        for(int p:vct){
            if(p<L[j]||p>R[j]) continue;
            mn=min(mn,p);
            mx=max(mx,p);
        }
        if(mx-mn<x){
            flag=false;
            break;
        }
    }
    return flag;
}

void solve(){
    cin>>n;
    s.clear();
    for(int i=1;i<=n;i++){
        string st;
        cin>>st;
        L[i]=s.length()+1;
        R[i]=s.length()+st.length();
        s+=st;
        s.push_back('#');    
    }
    getsa(s);
    int l=1,r=len,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

P4143 采集矿石

第一眼看上去好像没什么思路啊 www。考虑发掘性质，从大到小的话，如果我们选取的子串在不断扩大的话，排名会逐渐下降，但重要度因为是求和，所以是单调不减，我们考虑利用冰火战士的思路，两次二分出这个排名和重要度之和的交点，让后我们检查是否符合要求。

现在问题在于如何求某个子串在所有字符串本质不同子串的排名。所有本质不同子串的计算我们之前提到过，也就是：\left( \sum\limits_{i=1}^{|S|} n-p_{i}+1 \right)-\left(\sum\limits_{i=1}^{|S|-1} |\operatorname{LCP}(p_{i},p_{i+1})| \right)，但是如何求排名，我们考虑对于两个子串 s,t，对于 t 其字典序不大于 s 当且仅当 t 是 s 的前缀或者在去掉 LCP 后第一个字符大于后者。

两个条件，第一个条件对应的后缀排名是一段排名区间 [L,R],(L\le rk_{l}\le R)，满足第二种条件对应的就是 [R+1,n]。因此，求出排名为 [L,n] 的后缀本质不同的前缀数量，减去 r-l 重复算上的答案即为所求。求 L 考虑二分答案，找不大于 rk_{l} 的最小排名，使得排名在 [L,rk_{l}] 之间所有后缀的 LCP 不小于 r-l+1。通过 SA 加 ST 表即可做到 O(n \log^2 n)。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e6+15;
int n,v[MN],sumh[MN],sumsa[MN];
vector<pir> ans;
string s;

namespace SA{
 // 省略
 
    // 查询位置为 i 和 位置为 j 的后缀的 LCP
    int querylcp(int i,int j){
        int d=__lg(j-(i++));
        return min(ST[d][i],ST[d][j-(1<<d)+1]);
    }

    // 手动查询 ST 表
    int queryst(int l,int r){
        int d=__lg(r-l+1);
        return min(ST[d][l],ST[d][r-(1<<d)+1]);
    }

}using namespace SA;

int clac(int x,int y){
    int l=1,r=x=rk[x]+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(querylcp(mid,x)>=y) r=mid;
        else l=mid;
    }
    return sumsa[l]-sumh[l+1]-y+1;
}

signed main(){
    cin>>s;
    n=s.length();
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    getsa(s);
    initst();
    for(int i=n;i>=1;i--){
        sumh[i]=sumh[i+1]+ht[i];
        sumsa[i]=sumsa[i+1]+n-sa[i]+1;
    }
    for(int i=1;i<=n;i++) v[i]+=v[i-1];
    for(int i=1;i<=n;i++){
        int l=1,r=n-i+2;
        while(l+1<r){
            int mid=(l+r)>>1;
            if(clac(i,mid)>=v[i+mid-1]-v[i-1]) l=mid;
            else r=mid;
        }
        if(clac(i,l)==v[i+l-1]-v[i-1]){
            ans.push_back(pir(i,i+l-1));
        }
    }
    cout<<ans.size()<<'\n';
    for(auto p:ans) cout<<p.first<<" "<<p.second<<'\n';

    return 0;
}

练习

P4081 [USACO17DEC] Standing Out from the Herd P

P6640 [BJOI2020] 封印

P2408 不同子串

P5431

4.4 对串进行分块操作

P1117 [NOI2016] 优秀的拆分

显然 AABB 由两个形如 AA 的串拼接起来的，考虑维护两个数组 a_{i},b_{i}。其中 a_{i} 表示以 i 结尾有多少个 AA 串，b_{i} 表示以 i 开头有多少个 AA 串，通过乘法原理不难得出 ans=\sum\limits_{i=1}^{n-1}a_{i}b_{i+1}。

现在问题在于如何求解 a_{i},b_{i}，这里有一个很妙的 Trick 就是枚举长度，设置关键点求解 a,b。

对于固定的 L，若每间隔 L 放置一个关键点，则 AA 必然必然恰好经过两个关键点。让后考虑，我们只需要相邻两个关键点往前的 LCS 和往后的 LCP，若 LCS+LCP\ge len，那么就表示一定存在长度为 len 的 AA 串。不难发现，所有经过这两个关键点长度为 len 的 AA 串一定是连续的！我们可以找到这个区间，让后用前缀和差分，就可以避免区间修改了。现在问题转化为如何求解 LCS 和 LCP，正反串建立 SA 让后跑 ST 表就可以啦，时间复杂度是枚举 len 的调和级数，为 O(n\log^2 n)。

从这道题开始，设置关键点变成了经典套路。

下列代码 f\to a,g\to b。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int T,f[MN],g[MN];
string s;

struct SA{
    int len,sa[MN],x[MN],y[MN],rk[MN],c[MN],ht[MN],ST[30][MN];

 // 省略

    // ST表初始化
    void initst(){
        for(int i=1;i<30;i++){
            for(int j=1;j+(1<<i)-1<=len;j++){
                ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
            }
        }
    }

    // 查询位置为 i 和 位置为 j 的后缀的 LCP
    int querylcp(int i,int j){
        if((i=rk[i])>(j=rk[j])) swap(i,j);
        int d=__lg(j-(i++));
        return min(ST[d][i],ST[d][j-(1<<d)+1]);
    }

    // 手动查询 ST 表
    int queryst(int l,int r){
        int d=__lg(r-l+1);
        return min(ST[d][l],ST[d][r-(1<<d)+1]);
    }

}A,B;

void solve(){
    cin>>s;
    int n=s.length();
    A.getsa(s);
    A.initst();
    reverse(s.begin(),s.end());
    B.getsa(s);
    B.initst();
    for(int i=1;i<=n;i++){
        f[i]=g[i]=0;
    }
    for(int len=1;len<=(n>>1);len++){
        for(int l=len;l<=n;l+=len){
            int r=l+len,lcp=min(len,A.querylcp(l,r)),lcs=min(len-1,B.querylcp(n-(l-1)+1,n-(r-1)+1));
            if(lcp+lcs>=len){
                int cov=lcp+lcs-len+1;
                f[r+lcp-cov]++;
                f[r+lcp]--;
                g[l-lcs+cov]--;
                g[l-lcs]++;
            }
        }
    }
    for(int i=1;i<=n;i++) f[i]+=f[i-1],g[i]+=g[i-1];
    long long ans=0;
    for(int i=1;i<n;i++) ans+=1ll*f[i]*g[i+1];
    cout<<ans<<'\n';
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

SP687 REPEATS - Repeats

借助上面的套路，考虑枚举循环节长度 L，每相邻 L 个位置放置一个关键点。若某个长度为 k 的子串出现 k 次，那么恰好跨过 k 个关键点。

我们考虑二分 k，考虑所有连续 k 个关键点 p,p+L,p+2\times L,\dots,p+(k-1)L，若这些位置的 LCP 加上它们对应所有前缀的 LCS 减去同时覆盖关键点后的长度不小于 L，即 LCS+LCP-1\ge L，那么表示出现重复，考虑从小到大用长为 k 的块滑字符串，用单调队列维护排名最大值和最小值方便求解 LCS 与 LCP，时间复杂度 O(n \log^2 n)。

还可以更优化，我们当 L 固定的时候，一个大区间一定比任何子区间更优，那么也就表明右指针增加的时候左指针单调不降，考虑双指针代替二分，时间复杂度 O(n \log n)。

Alex_wei 的 Sol 3 看不懂 Orz。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN = 5e4 + 5;
int n;

struct SA {
    int len, sa[MN], x[MN], y[MN], rk[MN], c[MN], ht[MN], ST[16][MN];
// 省略
    int querylcp(int i, int j) {
        if((i = rk[i]) > (j = rk[j])) swap(i, j);
        int d = __lg(j - (i++));
        return min(ST[d][i], ST[d][j - (1 << d) + 1]);
    }
} A, B;

void solve() {
    cin >> n;
    string str;
    for(int i = 1; i <= n; i++) {
        char x;
        cin >> x;
        str.push_back(x);
    }
    A.getsa(str);
    A.initst();
    reverse(str.begin(), str.end());
    B.getsa(str);
    B.initst();
    
    int ans = 1;
    for(int len = 1; len <= n; len++) {
        for(int l = len, r = len + len; r <= n; l += len, r += len) {
            int lcp = A.querylcp(l, r);
            int lcs = B.querylcp(n - r + 1, n - l + 1);
            ans = max(ans, (lcp + lcs - 1) / len + 1);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

4.5 与DP贪心结合

这里我们是单独介绍一些利用贪心思路和 DP 思路求解的问题。一般来说，这里的问题 SA 不是主角，是起到一个打辅助的作用的。

CF822E Liar

一个显然的贪心，我们在新选择一个字符串并起来的时候应当尽可能的进行匹配，我们一定会匹配到第一个 k 使得 s_{i+k} \neq t_{j+k}，证明考虑反证法和调整法。

字符串匹配，之前做过一堆 KMP 的题，这里肌肉记忆设 f(i,j) 表示在 s 匹配前 i 个字符，匹配 t 到 j 的位置，选出最少的子串数量。根据数据范围显然会炸缸，注意到 x\le 30，考虑经典 Trick：状态互换，设 f(i,j) 表示在 s 匹配前 i 个字符，选出子串数 j，最多能匹配到 t 的哪个位置。对于每个 f(i,j) 可以转移到 f(i+1,j) 表示不开启匹配，若开启匹配，根据贪心思路，则需要找到 s[i+1,n] 和 t[f(i,j-1)+1,m] 的最长公共前缀 L，令 f(i+L,j) \leftarrow \max(f(i+L,j),f(i,j-1)+L)，求后缀的最长公共前缀是 SA 的拿手好戏，时间复杂度 O(nx+n \log n)。

DP 加贪心加 SA，很好的题啊！

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e5+15,MK=35;
int f[MN][MK],X,n,m;
string s,t,sst;


namespace SA{
// 省略

    int lcp(int i,int j){
        if((i=rk[i])>(j=rk[j])) swap(i,j);
        int d=__lg(j-(i++));
        return min(st[d][i],st[d][j-(1<<d)+1]);
    }

    int queryst(int l,int r){
        int d=__lg(r-l+1);
        return min(st[d][l],st[d][r-(1<<d)+1]);
    }

}using namespace SA;

int lcpst(int i,int j){
    if(i>n||j>m) return 0;
    j+=n+1;
    return lcp(i,j);
}

int main(){
    cin>>n>>s>>m>>t;
    sst=s+'#'+t;
    getsa(sst);
    initst();
    cin>>X;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=X;j++){
            int L=lcpst(i,f[i][j-1]+1);
            f[i+L][j]=max(f[i+L][j],f[i][j-1]+L);
            f[i+1][j]=max(f[i+1][j],f[i][j]);
        }
    }
    if(f[n+1][X]==m) cout<<"YES";
    else cout<<"NO";
    return 0;
}

P6095 [JSOI2015] 串分割

有一个贪心的想法就是我们贪心让最大位数最小。那么答案串的长度最多就是 L=\lceil \dfrac{n}{k} \rceil。贪心思路就是能断为 \lceil \dfrac{n}{k} \rceil 尽量断为 \lceil \dfrac{n}{k} \rceil，不然就断成 \lceil \dfrac{n}{k} \rceil-1，证明考虑反证法即可。

让后我们考虑如何比较字符串大小，考虑二分排名 rk，那么从 i 开始为 \lceil \dfrac{n}{k} \rceil / \lceil \dfrac{n}{k} \rceil-1 的串即为后缀 i 的前缀，又因为前缀的排名严格不大于原串，所以直接比较原后缀的排名与二分的排名即可。

最后要求输出最大值数字串，考虑存下排名的值输出这个排名的后缀长为 \lceil \dfrac{n}{k} \rceil 的前缀就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
int n,K;
string s;

namespace SA{
// 省略
}using namespace SA;

bool check(int mid){
    int len=n/K;
    for(int i=1;i<=len;i++){
        int st=i,cnt=0;
        for(int j=1;j<=K;j++){
            if(cnt<(n%K)&&rk[st]<=mid){
                st+=len+1;
                cnt++;
            }else st+=len;
        }
        if(st-i==n) return 1;
    }
    return 0;
}

signed main(){
    cin>>n>>K>>s;
    if(n%K==0){
        cout<<8;
        return 0;
    }
    s=s+s;
    getsa(s);
    int l=1,r=2*n;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    for(int i=1;i<=ceil(n*1.0/K);i++){
        cout<<s[sa[l]+i-1];
    }
    return 0;
}

4.6 与数据结构或离线算法结合

SP8093 莫队

先解决如何查一个查询串是多少个模板串的子串。我们考虑将所有模板串用分隔符连接起来跑 SA，那么查询串是一个模板串的子串，在 SA 上的范围表示的是一个区间的形式，这个区间的性质表示为 \operatorname{LCP}(s_{i},s_{j})=len，这个区间我们可以通过二分找出来左端点右端点。

让后第二个，查询区间颜色数，既然我们已经有了每一个查询串对应的 SA 区间，考虑莫队维护区间颜色数，让后就做完了。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
struct Query{
    int l,r,id;
}qry[MN];
int n,m,qtot,qlen,col[MN],sumc,cnt[MN],ans[MN];
vector<int> str;

namespace SA{
// 省略
    // 查询位置为 i 和 位置为 j 的后缀的 LCP
    int querylcp(int i,int j){
        int d=__lg(j-(i++));
        return min(ST[d][i],ST[d][j-(1<<d)+1]);
    }

    // 手动查询 ST 表
    int queryst(int l,int r){
        int d=__lg(r-l+1);
        return min(ST[d][l],ST[d][r-(1<<d)+1]);
    }

}using namespace SA;

bool cmp(Query x,Query y){
    if(x.l/qlen!=y.l/qlen) return x.l<y.l;
    return x.r<y.r;
}

void add(int x){
    cnt[col[x]]++;
    if(cnt[col[x]]==1) sumc++;
}

void del(int x){
    cnt[col[x]]--;
    if(!cnt[col[x]]) sumc--;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(auto c:s){
            str.push_back(c);
            col[str.size()]=i;
        }
        str.push_back('z'+i);
    }
    getsa(str);
    for(int i=1;i<=m;i++){
        int slen,L=1,R=len;
        string s;
        cin>>s;
        slen=s.length();
        s=" "+s;
        for(int j=1;j<=slen;j++){
            int l=L,r=R;
            while(l<=r){
                int mid=(l+r)>>1;
                if(str[sa[mid]+j-1]<s[j]) l=mid+1;
                else r=mid-1;
            }
            swap(l,L);
            r=R;
            while(l<=r){
                int mid=(l+r)>>1;
                if(str[sa[mid]+j-1]<=s[j]) l=mid+1;
                else r=mid-1;
            }
            R=r;
        }
        if(L<=R){
            qry[++qtot]={L,R,i};
        }
    }
    qlen=sqrt(len);
    sort(qry+1,qry+1+qtot,cmp);
    int l=1,r=0;
    for(int i=1;i<=qtot;i++){
        while(l<qry[i].l) del(sa[l++]);
        while(l>qry[i].l) add(sa[--l]);
        while(r<qry[i].r) add(sa[++r]);
        while(r>qry[i].r) del(sa[r--]);
        ans[qry[i].id]=sumc;
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

CF1608G Alphabetic Tree

1751547070838.png

因为信息具有可减性，战术将询问差分扫描线，即 Q(u,v,l,r) 拆为 Q(u,v,1,r)-Q(u,v,1,l-1)。

对于后缀数组，查一个查询串是多少个模板串的子串。我们考虑将所有模板串用分隔符连接起来跑 SA，那么查询串是一个模板串的子串，在 SA 上的范围表示的是一个区间的形式，这个区间的性质表示为 \operatorname{LCP}(s_{i},s_{j})=len，这个区间我们可以通过二分找出来左端点右端点。

那么对于本题来说也是一样的，我们对 s_i 进行后缀排序，设当前扫描线扫到位置 p，则管用的只有 s_{1\to p} 的后缀。那么对于一次询问 Q(u,v,1,p) 我们只需要对 u\to v 形成的字符串 t(u,v) 进行上述操作即可，具体的，我们考虑二分排名 k，问题转化为判定性问题比较 t(u,v) 和排名为 k 的后缀 s 的大小关系。一般的比较方法就是我们之前所以到过的：两个子串 s,t，对于 t 其字典序不大于 s 当且仅当 t 是 s 的前缀或者在去掉 LCP 后第一个字符大于后者。

但是本题上树了，我们必须要考虑哈希求解，那么这样的话我们必须求解出 s[1\to len] 的哈希值，以及 u\to v 长度为 len 的前缀的哈希值，后者要树上倍增，树上倍增加二分时间复杂度 O(q \log^3 n)，改造成倍增二分 O(q \log^2 n) 即可通过。

巨大码农，代码。

[P4094 HEOI2016字符串]

又是最长公共子串，好烦啊~

直接二分长度，让后问题转化为判定性问题，那么一个长度可行当且仅当：

  • 开头在 [a,b-mid+1]
  • \operatorname{LCP(s,c)}\ge mid，其中 c 为题目中 s[c\to d]。

那么问题转化为询问满足以上两个条件的后缀 suf_{k} 的个数是否大于 0，同时子串出现次数前面提到好多次了，一定是在后缀数组上连续的区间，二分左端点右端点即可，现在两个问题都是静态区间询问，主席树做即可。

我主席树又写错了，希望大家认真实现，我已经做麻了呜呜呜。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
int n,m;
string s;

struct Segment{
#define ls t[p].lson
#define rs t[p].rson
    
    struct Node{
        int lson,rson,val;
    }t[MN*20+1145];
    int rt[MN],tot;

    int insert(int lst,int l,int r,int x){
        int p=++tot;
        t[p]=t[lst];
        t[p].val++;
        if(l==r) return p;
        int mid=(l+r)>>1;
        if(x<=mid) t[p].lson=insert(t[lst].lson,l,mid,x);
        else t[p].rson=insert(t[lst].rson,mid+1,r,x);
        return p;
    }

    int query(int u,int v,int l,int r,int fl,int fr){
        if(l>=fl&&r<=fr){
            return t[v].val-t[u].val;
        }
        int mid=(l+r)>>1,ret=0;
        if(mid>=fl) ret+=query(t[u].lson,t[v].lson,l,mid,fl,fr);
        if(mid<fr) ret+=query(t[u].rson,t[v].rson,mid+1,r,fl,fr);
        return ret;
    }

    int query(int u,int v,int l,int r){
        return query(rt[u-1],rt[v],1,n,l,r);
    }

#undef ls
#undef rs
}sg;

namespace SA{
    int len,sa[MN],x[MN],y[MN],rk[MN],c[MN],ht[MN],ST[30][MN];

 // 省略

    // ST表初始化
    void initst(){
        for(int i=1;i<30;i++){
            for(int j=1;j+(1<<i)-1<=len;j++){
                ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
            }
        }
    }

    // 查询位置为 i 和 位置为 j 的后缀的 LCP
    int querylcp(int i,int j){
        int d=__lg(j-(i++));
        return min(ST[d][i],ST[d][j-(1<<d)+1]);
    }

    // 手动查询 ST 表
    int queryst(int l,int r){
        int d=__lg(r-l+1);
        return min(ST[d][l],ST[d][r-(1<<d)+1]);
    }

}using namespace SA;

bool check(int x,int a,int b,int c){
    int l=1,r=rk[c],L,R;
    while(l<r){
        int mid=(l+r)>>1;
        if(querylcp(mid,rk[c])<x) l=mid+1;
        else r=mid;
    }
    L=r;
    l=rk[c],r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(querylcp(rk[c],mid)<x) r=mid-1;
        else l=mid;
    }
    R=r;
    return sg.query(L,R,a,b-x+1)>0;
}

void solve(int a,int b,int c,int d){
    int l=0,r=min(b-a+1,d-c+1);
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid,a,b,c)) l=mid;
        else r=mid-1;
    }
    cout<<r<<'\n';
}

signed main(){
    cin>>n>>m>>s;;
    getsa(s);
    initst();
    for(int i=1;i<=n;i++){
        sg.rt[i]=sg.insert(sg.rt[i-1],1,n,sa[i]);
    }
    while(m--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        solve(a,b,c,d);
    }
    return 0;
}

P2336 [SCOI2012] 喵星球上的点名

将姓和名用分隔符连接，问题相当于给定 n 个文本串和 m 个模式串，对每个文本串求出作为其子串的模式串数量，这是 AC 自动机应用，但是字符集太大了不太好做。

将所有文本串用分隔符后建后缀数组，对每个模式串求出以其为前缀的排名区间，这个讲过 100 万遍了不再重复。第一位就是问区间颜色数，考虑离线下来跑莫队或者扫描线 BIT，第二问相当于对每种颜色查询与其有交的区间数。对每个区间和每个颜色在第一个位置统计答案，则每个位置对其颜色贡献在左端点落一个区间，右端点落另一端区间的区间数量，这是二位数点，还是扫描线 BIT。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+15, INF=1e9;

int nn, q, n, m=400000;
int sa[N], ra[N], h[N], t1[N], t2[N], c[N];
int st[20][N], lg[N];
int s[N], col[N], hd[N], len[N], bu[N];
int pre[N], ans1[N], ans2[N];
int lp[N]; 
struct Query { int id, l, r; } qry[N];

struct BIT {
    int t[N];
    
    void clear() {
        memset(t, 0, sizeof(t));
    }
    
    void upd(int i, int v) {
        if (i) for (; i<=n; i+=i&-i) t[i] += v;
    }
    
    int query(int i) {
        int res = 0;
        for (; i; i-=i&-i) res += t[i];
        return res;
    }
    
    int query(int l, int r) {
        return query(r) - query(l-1);
    }
} bit1, bit2;

void getsa() {
// 省略
}

void geth() {
// 省略
}

void initST() {
// 省略
}

int getmin(int a, int b) {
    if (a == b) return INF;
    if (a > b) swap(a, b);
    int d = lg[b-(a++)];
    return min(st[d][a], st[d][b-(1<<d)+1]);
}

bool cmp(Query a, Query b) {
    return a.r < b.r;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> nn >> q;
    int x, c = 10000;
    for (int i=1; i<=nn; ++i) {
        for (int j=0; j<2; ++j) {
            int len; cin >> len;
            while (len--) {
                cin >> x;
                s[++n] = x;
                col[n] = i;
            }
            s[++n] = ++c;
        }
    }
    for (int i=1; i<=q; ++i) {
        cin >> len[n+1];
        hd[n+1] = i;
        for (int j=len[n+1]; j--; ) {
            cin >> x;
            s[++n] = x;
            col[n] = -i;
        }
        s[++n] = ++c;
    }
    getsa();
    geth();
    initST();
    for (int i=1; i<=n; ++i) {
        if (col[sa[i]] > 0) {
            pre[i] = bu[col[sa[i]]];
            bu[col[sa[i]]] = i;
        }
        if (hd[i]) {
            qry[hd[i]].id = hd[i];
            int l=1, r=ra[i];
            while (l < r) {
                int mi = (l+r)>>1;
                if (getmin(mi, ra[i]) >= len[i]) r = mi;
                else l = mi+1;
            }
            qry[hd[i]].l = lp[hd[i]] = l;
            l = ra[i], r = n;
            while (l < r) {
                int mi = (l+r+1)>>1;
                if (getmin(ra[i], mi) >= len[i]) l = mi;
                else r = mi-1;
            }
            qry[hd[i]].r = r;
        }
    }
    sort(qry+1, qry+q+1, cmp);
    sort(lp+1, lp+q+1);
    for (int i=1, j=1, k=1; i<=n; ++i) {
        for (; j<=q && lp[j]==i; ++j) bit2.upd(i, 1);
        if (col[sa[i]] > 0) {
            ans2[col[sa[i]]] += bit2.query(i) - bit2.query(pre[i]);
            bit1.upd(i, 1);
            bit1.upd(pre[i], -1);
        }
        for (; k<=q && qry[k].r==i; ++k) {
            ans1[qry[k].id] = bit1.query(qry[k].l, qry[k].r);
            bit2.upd(qry[k].l, -1);
        }
    }
    for (int i=1; i<=q; ++i) cout << ans1[i] << "\n";
    for (int i=1; i<=nn; ++i) cout << ans2[i] << " ";
    return 0;
}

4.7 与其他结合

CF1654F Minimal String Xoration

关键性质：位运算在每一位独立。

设 f(i,d) 表示 s 下表异或 i 得到字符串的前 2^d 位，那么有 f(i,d+1)=f(i,d)+f(i\oplus 2^d,d)。类似于后缀排序，设 rk(i,d) 表示 f(i,d) 在所有 f(j,d)(0\le j \le 2^n) 中的排名，则 p(i,d+1) 就是二元组 (p(i,d),p(i\oplus 2^d ,d)) 在所有二元组 (p(j,d),p(j \oplus 2^d,d)) 中的排名。

倍增计数排序 O(2^n n) 即可。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,m,v,a[MN],b[MN],c[MN];
string s;

bool cmp(int x,int y){
    if(b[x]==b[y]) return b[x^v]<b[y^v];
    return b[x]<b[y];
}

int main(){
    cin>>n>>s;
    m=1<<n;
    for(int i=0;i<m;i++) a[i]=i,b[i]=s[i]-'a';
    sort(a,a+m,cmp);
    for(int i=1;i<=n;i++){
        v=(1<<(i-1));
        sort(a,a+m,cmp);
        int cnt=0;
        for(int j=0;j<m;j++){
            if(j==0||cmp(a[j-1],a[j])) c[a[j]]=++cnt; 
            else c[a[j]]=cnt;
        }
        for(int j=0;j<m;j++) b[j]=c[j];
    }
    for(int i=0;i<m;i++) cout<<s[i^a[0]];
}

GYM102803E Everybody Lost Somebody

给同学做了，好题。

给出 SA 数组和 Height 数组我们能得到什么信息，具体来说：

  • 对于 2\le i \le n，有 s[sa_{i-1}]\le s[sa_{i}]。更进一步，若 rk_{sa(i-1)+1}>rk_{sa(i)+1}，则必须有 s[sa_{i-1}] < s[sa_{i}]。
  • 对于 2\le i \le n，对于 0\le j \le ht_{i}，有 s[sa_{i-1}+j]\le s[sa_{i}+j]。更进一步，若 sa_{i-1}+ht_{i}\le n，则必须有 s[sa_{i-1}+ht_{i}] < s[sa_{i}+ht_{i}]。

对于 ht_{i}\neq -1，枚举 j\in [0,ht_{i})，则 s[sa_{i}+j]=s[sa_{i+1}+j] 且 s[sa_{i}+ht_{i}]<s[sa_{i+1}+ht_{i}]。我们可以对于等于并查集缩点，小于连边跑拓扑即可。

现在考虑 ht_{i}=-1 的情况，此时对于 sa_{i},sa_{i+1} 的LCP 没有限制，而唯一的限制在于 suf_{sa(i)}<suf_{sa(i+1)}，这对 s[sa_{i}],s[sa_{i+1}] 提出了要求。当 rk(sa_{i}+1)<rk(sa_{i+1}+1) 时，s[sa_i] 只要不大于 s[sa_{i+1}]，否则 s[sa_i] 需要小于s[sa_{i+1}]。还是拓扑排序，时间复杂度 O(n^2)。

进一步可以发现，只要在合并的时候保持后缀大小顺序的连边，就可以通过了。时间复杂度 O(n \log n)，魏老师有 O(n) 看不懂 qwq。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=5200;
int n,sa[MN],rk[MN],pre[MN],ht[MN];
char ans[MN];
vector<int> G[MN];

int root(int x){
    if(pre[x]==x) return pre[x];
    else return pre[x]=root(pre[x]);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sa[i];
        rk[sa[i]]=i;
        pre[i]=i;
    }
    for(int i=2;i<=n;i++){
        cin>>ht[i];
    }
    for(int i=2;i<=n;i++){
        if(ht[i]==-1){
            int x=sa[i-1]+1,y=sa[i]+1;
            if(rk[x]>rk[y]) G[sa[i]].push_back(sa[i-1]); 
        }
        else{
            int x=sa[i-1],y=sa[i];
            for(int j=1;j<=ht[i];j++){
                pre[root(x+j-1)]=pre[root(y+j-1)];
            }
            if(x+ht[i]<=n) G[y+ht[i]].push_back(x+ht[i]);
        }
    }
    ans[sa[1]]='a';
    for(int i=2;i<=n;i++){
        ans[sa[i]]=ans[sa[i-1]];
        for(auto v:G[sa[i]]){
            if(ans[v]+1>ans[sa[i]]) ans[sa[i]]=ans[v]+1;
        }
        for(int j=1;j<n;j++){
            if(root(sa[j])==root(sa[i])) ans[sa[j]]=ans[sa[i]];
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[i];
    return 0;
}

5. 后缀数组变形-树上后缀数组

P5353

可以参考 STARSczy题解的思路，这里我就不再详细展开了（打字太累了）

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,fa[MN],rk[MN],c[MN],sa[MN],x[MN],y[MN],tmp[MN];
string s;
vector<int> adj[MN];

namespace SAonTree{
    void dfs(int u){
        rk[u]+=c[rk[u]]++;
        sort(adj[u].begin(),adj[u].end());
        for(int v:adj[u]) dfs(v);
    }

    void getsa(string s){
        int len=s.length();
        memset(c,0,sizeof(c));
        for(int i=1;i<=len;i++) c[s[i-1]+1]++;
        for(int i=1;i<=1000;i++) c[i]+=c[i-1];
        for(int i=1;i<=len;i++) rk[i]=c[s[i-1]]+1;
        for(int w=0;w<=__lg(len);w++){
            memset(c,0,sizeof(c));
            memset(tmp,0,sizeof(tmp));
            for(int i=1;i<=len;i++){
                x[i]=rk[i];
                y[i]=rk[fa[i]];
                c[y[i]+1]++;
            }
            for(int i=1;i<=len;i++) c[i]+=c[i-1];
            for(int i=1;i<=len;i++) tmp[++c[y[i]]]=i;
            memset(c,0,sizeof(c));
            for(int i=1;i<=len;i++) rk[tmp[i]]+=c[x[tmp[i]]]++;
            for(int i=1;i<=len;i++) sa[rk[i]]=i;
            for(int i=1;i<=len;i++){
                if(x[sa[i-1]]==x[sa[i]] && y[sa[i-1]]==y[sa[i]])
                    rk[sa[i]]=rk[sa[i-1]];
            }
            for(int i=len;i>=1;i--) fa[i]=fa[fa[i]];
        }
        
        memset(c,0,sizeof(c));
        dfs(1);
        for(int i=1;i<=len;i++) sa[rk[i]]=i;
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        adj[fa[i]].push_back(i);
    }
    cin>>s;
    SAonTree::getsa(s);
    for(int i=1;i<=n;i++) cout<<sa[i]<<" ";
    return 0;
}

例题：

P5346

假设我们求出来了 n 个人的排名。

  • 操作 1：O(1) 回答。
  • 操作 2：考虑主席树求第 k 小，只需要在节点的父亲版本上更新即可。O(\log n) 回答
  • 操作 3：按照 DFN 序更新即可。O(\log n) 回答。
    而排名求解利用树上后缀数组即可：
#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e6+15;
int n,q,fa[MN],a[MN],b[MN],tot;
vector<int> adj[MN],s;

struct Segment{
#define ls t[p].lson
#define rs t[p].rson
    struct Node{
        int lson,rson,val;
    }t[MN*20+1145];
    int tot,rt[MN];

    int insert(int lst,int l,int r,int x){
        int p=++tot;
        t[p]=t[lst];
        t[p].val+=1;
        if(l==r) return p;
        int mid=(l+r)>>1;
        if(mid>=x) ls=insert(t[lst].lson,l,mid,x);
        else rs=insert(t[lst].rson,mid+1,r,x);
        return p;
    }

    int query(int u,int v,int l,int r,int k){
        if(l==r) return l;
        int mid=(l+r)>>1;
        int rz=t[t[v].rson].val-t[t[u].rson].val;
        if(k<=rz) return query(t[u].rson,t[v].rson,mid+1,r,k);
        return query(t[u].lson,t[v].lson,l,mid,k-rz);
    }

#undef ls
#undef rs
}sg0,sg1;

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

namespace SAonTree{
    int rk[MN],c[MN],tmp[MN],x[MN],y[MN],sa[MN];

    void dfs(int u){
        rk[u]+=c[rk[u]]++;
        sort(adj[u].begin(),adj[u].end());
        for(int v:adj[u]) dfs(v);
    }

    void getsa(vector<int> s){
        int len=s.size();
        memset(c,0,sizeof(c));
        for(int i=1;i<=len;i++) c[s[i-1]+1]++;
        for(int i=1;i<=5e5;i++) c[i]+=c[i-1];
        for(int i=1;i<=len;i++) rk[i]=c[s[i-1]]+1;
        for(int w=0;w<=__lg(len);w++){
            memset(c,0,sizeof(c));
            memset(tmp,0,sizeof(tmp));
            for(int i=1;i<=len;i++){
                x[i]=rk[i];
                y[i]=rk[fa[i]];
                c[y[i]+1]++;
            }
            for(int i=1;i<=len;i++) c[i]+=c[i-1];
            for(int i=1;i<=len;i++) tmp[++c[y[i]]]=i;
            memset(c,0,sizeof(c));
            for(int i=1;i<=len;i++) rk[tmp[i]]+=c[x[tmp[i]]]++;
            for(int i=1;i<=len;i++) sa[rk[i]]=i;
            for(int i=1;i<=len;i++){
                if(x[sa[i-1]]==x[sa[i]] && y[sa[i-1]]==y[sa[i]])
                    rk[sa[i]]=rk[sa[i-1]];
            }
            for(int i=len;i>=1;i--) fa[i]=fa[fa[i]];
        }
        
        memset(c,0,sizeof(c));
        dfs(1);
        for(int i=1;i<=len;i++) sa[rk[i]]=i;
        for(int i=1;i<=n;i++){
            a[i]=rk[i];
        }
    }
}using namespace SAonTree;

namespace Tree{
    int siz[MN],dfn[MN],dtot;

    void dfsTree(int u){
        dfn[u]=++dtot;
        siz[u]=1;
        sg1.rt[dfn[u]]=sg1.insert(sg1.rt[dfn[u]-1],1,n,a[u]);
        for(auto v:adj[u]){
            sg0.rt[v]=sg0.insert(sg0.rt[u],1,n,a[v]);
            dfsTree(v);
            siz[u]+=siz[v];
        }
    }

}using namespace Tree;

int main(){
    read(n,q);
    for(int i=2;i<=n;i++){
        read(fa[i]);
        adj[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        read(a[i]);
        b[++tot]=a[i];
    }
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
        s.push_back(a[i]);
    }
    getsa(s);
    sg0.rt[1]=sg0.insert(0,1,n,a[1]);
    dfsTree(1);
    while(q--){
        int op,x,k;
        read(op,x);
        if(op==1){
            put(n+1-a[x]);
        }else if(op==2){
            read(k);
            put(sa[sg0.query(0,sg0.rt[x],1,n,k)]);
        }else{
            read(k);
            put(sa[sg1.query(sg1.rt[dfn[x]-1],sg1.rt[dfn[x]+siz[x]-1],1,n,k)]);
        }
    }
    return 0;
}

6. 后言

实际上，我们一些技巧基本都体现了我们开头所提到的增量法与势能分析，通过已求信息逐步推导新信息。一些技巧例如关键点思想或并查集块合并通过将全局问题转化为局部问题，动态问题转化为静态问题。

蒟蒻到这里就是已经基本学完了后缀数组了吧……不知道还有没有更好的题，但是常见的思路大概就以上几种，希望大家能够好好吸收，争取取得好成绩！

参考

2025.6.26模拟赛-来点不一...

评论