可能更洛谷的阅读体验

0. 前言

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

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

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

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

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

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

一些基本约定：

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

前后缀：

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

我们先从概念讲起。

1. 后缀树与后缀数组

1.1 朴素后缀树

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

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

image.png

若要在字符串上找一个子串是否出现，如"mam"\texttt{"mam"}，只需要在后缀树上查找就可以啦。

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

1.2 后缀数组

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

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

后缀sufisuf_i下表ii字典序后缀数组sajsa_j下表jj
"vamamadn"\texttt{"vamamadn"}1"adn"\texttt{"adn"}61
"amamadn"\texttt{"amamadn"}2"amadn"\texttt{"amadn"}42
"mamadn"\texttt{"mamadn"}3"amamadn"\texttt{"amamadn"}23
"amadn"\texttt{"amadn"}4"dn"\texttt{"dn"}74
"madn"\texttt{"madn"}5"madn"\texttt{"madn"}55
"adn"\texttt{"adn"}6"mamadn"\texttt{"mamadn"}36
"dn"\texttt{"dn"}7"n"\texttt{"n"}87
"n"\texttt{"n"}8"vamamadn"\texttt{"vamamadn"}18

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

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

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

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

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

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

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

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

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

wvfs4863.webp

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

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

10p32jao.webp

第四次：

zexkcukf.webp

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

再看一遍整体的过程：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 数组，我们这里简称为htht。

1.3 Height 数组

回顾 LCP 的定义：

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

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

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

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

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

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

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

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

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

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

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

ht(rku)≥ht(rku−1)−1ht(rk_{u})\ge ht(rk_{u-1})-1

我们这里引用 Alex_Wei 的图：

X2eJYj.png

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

1
2
3
4
5
6
7
8
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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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字符加密

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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。

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

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

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

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

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

例题：「USACO07DEC」Best Cow Line。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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

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

结论如下：

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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 的图：

Tt6Les.png

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

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

image.png

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

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

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

3.2 求本质不同子串数

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

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

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

(∑i=1∣S∣n−pi+1)−(∑i=1∣S∣−1∣LCP⁡(pi,pi+1)∣)\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∣)O(|S|) 求出。

3.3 多个串的最长公共子串

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

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

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

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

3.4 结合并查集

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

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

3.5 连续的若干个相同子串

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

4. 例题

4.1 并查集技巧

P2852 [USACO06DEC] Milk Patterns G

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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] 品酒大会

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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+ba+b 拼接后形成的字符串进行后缀数组操作。我们有一个贪心的想法，我们每次修改两个 LCP 尽量长的子串，这个贪心显然正确的，证明考虑反证法即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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」拜神

形式化题面如下：

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

1≤n≤5×104,1≤q≤1051\le n \le 5\times 10^4,1\le q \le 10^5。

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

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

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

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

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

请注意二分的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#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 的式子：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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

问题即求：

∑i=1K∑j=i+1KLCP⁡(sufi,sufj)\sum_{i=1}^{K} \sum_{j=i+1}^{K} \operatorname{LCP}\left(suf_{i}, suf_{j}\right)

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

∑i=1K∑j=i+1KLCP⁡(si,sj)=∑i=1K∑j=i+1Kmin⁡ri+1≤k≤rj{ htk}\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\}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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。

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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!

前面两问都比较好说，问题在于后面的限制，它是两个限制。我们考虑只有一个限制，比如说 LCP 的限制，显然我们可以根据之前我们提到的，并查集的思路，从小往大插，就可以满足LCP⁡(i,j)≤k1\operatorname{LCP}(i,j) \le k1，升级版之后我们又多了一个限制，这种限制在询问上表现的是一个范围，我们可以对第二个限制离线下来扫描线加并查集启发式合并做，这样做是O(nlog⁡3n)O(n \log^3 n) 而且不用说就能感觉非常难写，有没有什么好用的性质来简化问题呢？

观察LCP⁡(i,j),LCS⁡(i,j)\operatorname{LCP}(i,j),\operatorname{LCS}(i,j) 的性质，拼接起来形成长为LCP⁡(i,j)+LCS⁡(i,j)−1\operatorname{LCP}(i,j)+\operatorname{LCS}(i,j)-1 的相同子串，我们考虑关键点 Trick，我们在(i−LCP⁡(i,j)+1,j−LCS⁡(i,j)+1)(i-\operatorname{LCP}(i,j)+1,j-\operatorname{LCS}(i,j)+1) 统计贡献。因为相同子串要求极长，考虑枚举i,ji,j，若si−1≠sj−1s_{i-1}\neq s_{j-1}，则s[i,i+LCP⁡(i,j)−1]s[i,i+\operatorname{LCP}(i,j)-1] 产生贡献。我们发现因为我们在枚举，其实这个和 LCP 是无关了，不妨设f(x)=∑i=1xi(x−i+1)[i≤k1][j≤k2]f(x)=\sum\limits_{i=1}^x i(x-i+1)[i \le k1][j\le k2]，那么拆贡献有：

ans=∑1≤i≤j≤n[si−1≠sj−1]f(LCP⁡(rki,rkj))=∑k=1nf(k)∑1≤i<j≤n[LCP⁡(rki,rkj)=k,si−1≠j−1]=∑k=1nf(k)∑1≤i<j≤n[LCP⁡(i,j)=k,ssai−1≠saj−1]\begin{aligned} ans& = \sum_{1\le i \le j \le n}[s_{i-1}\neq s_{j-1}]f(\operatorname{LCP}(rk_i,rk_j)) \\ & = \sum_{k=1}^n f(k)\sum_{1\le i < j \le n}[\operatorname{LCP}(rk_i,rk_j)=k,s_{i-1}\neq _{j-1}] \\ & = \sum_{k=1}^n f(k)\sum_{1\le i < j \le n}[\operatorname{LCP}(i,j)=k,s_{sa_i-1}\neq _{sa_j -1}] \\ \end{aligned}

前面和后面都很好处理，中间的 LCP 用单调栈即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
constexpr int MN=1e6+15;
int k1,k2,n,st[MN],top,w[MN];
ull ans,f[MN];
string s;

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

    template<typename vct>
    void getsa(vct &s){
        int m=40000;
        len=s.size();
        s.insert(s.begin(),0);
        for(int i=1;i<=len;i++){
            x[i]=s[i];
            ++c[x[i]];
        }
        for(int i=1;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=1;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(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]]=k;
        }
    }

} using namespace SA;

ull calc1(int x){
    return x*(x+1)/2;
}

ull calc2(int x){
    return x*(x+1)*(x+x+1)/6;
}


ull solve(char lim) {
    ull cur = 0, ans = 0;
    top=0;
    memset(w,0,sizeof(w));
    for(int i = 2; i <= n; i++) {
        int wid = lim ? s[sa[i - 1] - 1] == lim : 1;
        while(top && st[top] >= ht[i]) {
            cur -= 1ull * w[top] * f[st[top]];
            wid += w[top--];
        }
        st[++top] = ht[i];
        w[top] = wid;
        cur += 1ull * wid * f[ht[i]];
        if(lim ? s[sa[i] - 1] == lim : 1) {
            ans += cur;
        }
    }
    return ans;
}

signed main(){
    cin>>s>>k1>>k2;
    n=s.length();
    for(int i=1;i<=n;i++){
        int l=max(1ll,i-k2+1),r=min(i,k1);
        if(l>r) break;
        f[i]=(calc1(r)-calc1(l-1))*(i+1)-(calc2(r)-calc2(l-1));
    }
    getsa(s);
    ans+=solve(0);
    for(int i=0;i<26;i++) ans-=solve('a'+i);
    cout<<ans;
    return 0;
}

练习

CF1073G

[HAOI2016]找相同字符

4.3 SA加速匹配和查询子串

P3763 [TJOI2017] DNA

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

二分加哈希：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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 有讲两种做法。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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，让后问题转化为求所有子串最长公共子串，考虑二分，只要有nn 个≥L\ge L 的htht 并且这几个都属于不同的串就可以啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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 个子问题：

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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。考虑发掘性质，从大到小的话，如果我们选取的子串在不断扩大的话，排名会逐渐下降，但重要度因为是求和，所以是单调不减，我们考虑利用冰火战士的思路，两次二分出这个排名和重要度之和的交点，让后我们检查是否符合要求。

现在问题在于如何求某个子串在所有字符串本质不同子串的排名。所有本质不同子串的计算我们之前提到过，也就是：(∑i=1∣S∣n−pi+1)−(∑i=1∣S∣−1∣LCP⁡(pi,pi+1)∣)\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,ts,t，对于tt 其字典序不大于ss 当且仅当tt 是ss 的前缀或者在去掉 LCP 后第一个字符大于后者。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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 的串拼接起来的，考虑维护两个数组ai,bia_{i},b_{i}。其中aia_{i} 表示以ii 结尾有多少个 AA 串，bib_{i} 表示以ii 开头有多少个 AA 串，通过乘法原理不难得出ans=∑i=1n−1aibi+1ans=\sum\limits_{i=1}^{n-1}a_{i}b_{i+1}。

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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

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

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

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

Alex_wei 的 Sol 3 看不懂 Orz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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=⌈nk⌉L=\lceil \dfrac{n}{k} \rceil。贪心思路就是能断为⌈nk⌉\lceil \dfrac{n}{k} \rceil 尽量断为⌈nk⌉\lceil \dfrac{n}{k} \rceil，不然就断成⌈nk⌉−1\lceil \dfrac{n}{k} \rceil-1，证明考虑反证法即可。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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 上的范围表示的是一个区间的形式，这个区间的性质表示为LCP⁡(si,sj)=len\operatorname{LCP}(s_{i},s_{j})=len，这个区间我们可以通过二分找出来左端点右端点。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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

哈哈其实没有那么多啦，我实现的时候其实也就不到 300 行吧，其实就是板子加板子，只是不过我是晚上写的太困了调了一万年。

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

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

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

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

巨大码农，代码。

[P4094 HEOI2016字符串]

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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] 喵星球上的点名

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#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)f(i,d) 表示ss 下表异或ii 得到字符串的前2d2^d 位，那么有f(i,d+1)=f(i,d)+f(i⊕2d,d)f(i,d+1)=f(i,d)+f(i\oplus 2^d,d)。类似于后缀排序，设rk(i,d)rk(i,d) 表示f(i,d)f(i,d) 在所有f(j,d)(0≤j≤2n)f(j,d)(0\le j \le 2^n) 中的排名，则p(i,d+1)p(i,d+1) 就是二元组(p(i,d),p(i⊕2d,d))(p(i,d),p(i\oplus 2^d ,d)) 在所有二元组(p(j,d),p(j⊕2d,d))(p(j,d),p(j \oplus 2^d,d)) 中的排名。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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≤i≤n2\le i \le n，有s[sai−1]≤s[sai]s[sa_{i-1}]\le s[sa_{i}]。更进一步，若rksa(i−1)+1>rksa(i)+1rk_{sa(i-1)+1}>rk_{sa(i)+1}，则必须有s[sai−1]<s[sai]s[sa_{i-1}] < s[sa_{i}]。
  • 对于2≤i≤n2\le i \le n，对于0≤j≤hti0\le j \le ht_{i}，有s[sai−1+j]≤s[sai+j]s[sa_{i-1}+j]\le s[sa_{i}+j]。更进一步，若sai−1+hti≤nsa_{i-1}+ht_{i}\le n，则必须有s[sai−1+hti]<s[sai+hti]s[sa_{i-1}+ht_{i}] < s[sa_{i}+ht_{i}]。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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题解的思路，这里我就不再详细展开了（打字太累了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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

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

  • 操作 1：O(1)O(1) 回答。
  • 操作 2：考虑主席树求第kk 小，只需要在节点的父亲版本上更新即可。O(log⁡n)O(\log n) 回答
  • 操作 3：按照 DFN 序更新即可。O(log⁡n)O(\log n) 回答。
    而排名求解利用树上后缀数组即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#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. 后言

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

字符串后缀，是字符串的大杀器，在做题过程中，我们能够体会到后缀独特的性质，能够将我们必须暴力枚举的子串简单化，并且将它的对立面——前缀联系起来，后缀数组这一利器，能够解决大部分的问题，但是，有一些问题是后缀数组所不能解决的。这个时候，就要出动我们的 SAM 啦，敬请期待，字符串终极神器——后缀自动机 - 洛谷专栏。

UPD on 2025.7.7：孩子们，我题全部都做完了，结果练 SAM 发现题单里的题都用后缀数组实现过一遍了，充分证明了 SA 可以替代大部分 SAM。然而不是这样的。

完结撒花！

参考