字符串总结

（施工中）

感谢 DeepSeek 对本文写作的大力支持。

字符串

字符串是一串顺序排列的字符。（废话）

以下是一些有关字符串的定义：

• 下标（index）：位于字符串第 个位置的字符下标为 （本文采用 1-index）。
• 子串（substring）：对于任意 取出下标范围为 的字符依次排列即为一个子串，记为 。
• 子序列（subsequence）：对于任意 依次取出 排列即为一个子序列。
• 前缀（prefix）：任意以 开头的子串。特别的，当 时，称之为真前缀。
• 后缀（suffix）：任意以 结尾的子串。特别的，当 时，称之为真后缀。
• 字典序：对于任意两个字符串 ，，称 字典序小于 当且仅当满足以下两个条件之一：
• • 存在一个下标 ，使得 ，且 。
• • 。
• 回文：如果一个字符串等于它的翻转，称它为回文串。

哈希

哈希即映射算法，是整个 OI 界性价比最高的算法几乎没有之一，搭配二分食用后它可以用几乎为零的学习成本和较高的效率解决下文大部分高级算法能解决的问题。

映射

我们知道双射的定义：对于集合 ，如果存在关系 使得 中任意一个元素都在 中存在且仅存在一个元素与之对应，这个映射就是一个双射。

但是真的要找这样的算法是非常难的，因此我们退一步，如果我们认为这个关系只有极小的概率能让 中两个不同元素经过关系后得到相同的结果，那么它就是一个合适的哈希算法。

生活中存在一些这样的哈希算法，比如将快递映射到取件码，将学生映射到学号；也存在一些会发生冲突的哈希算法，比如如果将首字母作为一个人名字的哈希值，就会出现诸如“主席树”之类令人忍俊不禁的情况。

哈希的主要用途是牺牲极小的正确率，将原本需要高时间复杂度比较的元素映射到低时间复杂度比较。这个牺牲的正确率一般是可以计算的：如果将 个元素映射到 个空间，那么发生冲突的概率为 ；但是如果将 个元素映射到 个空间，就有高达 的概率发生冲突（生日悖论）。因此选取合适的哈希算法与映射后的空间极为重要。

字符串哈希

字符串哈希是典型的降低比较时间复杂度的算法。

考虑下列问题：

求模式串 在文本串 中的出现次数。

如果使用朴素算法，就需要对字符串的每个位置都进行一次时间复杂度 的匹配，最坏时间复杂度会达到 。但是使用字符串哈希，就能将单次匹配的时间复杂度降低为 ，总时间复杂度 。

常用的字符串哈希实际上进行了两次映射：先将字符串映射为 （字符集大小）进制数，然后再用取模等方式将其映射到常常为 位无符号整数的大小。

关于哈希的具体写法不再赘述。

// 1-indexed
const ll HM[2] = {1000000007, 1000000009};
const ll HB[2] = {911382629, 19260817};
const int M = 1e6 + 5;
// 1-indexed string

ull hb[2][M];

void init_hsh() {
    for (int j = 0; j < 2; ++j) {
        hb[j][0] = 1;
        for (int i = 1; i < M; ++i)
            hb[j][i] = hb[j][i - 1] * HB[j] % HM[j];
    }
}

typedef std::array<ull,2> pul;
template <typename Tp>void cmod(Tp &x,int p){x=(x%p+p)%p;}
struct shsh{
    private:
        vul h[2];
    public:
        shsh(int n,string s):h{vul(n+1),vul(n+1)}{
            for(int j=0;j<2;++j)
                for(int i=1;i<=n;++i)
                    h[j][i]=(h[j][i-1]*HB[j]%HM[j]+s[i])%HM[j];
        }
        pul hsh(int l,int r){
            int len=r-l+1;
            pul x;
            for(int i=0;i<2;++i){
                auto p=h[i][l-1]*hb[i][len]%HM[i];
                cmod(x[i]=h[i][r]+HM[i]-p,HM[i]);
            }
            return x;
        }
};

ACAM

（别问我为什么没有 KMP，你都会 ACAM 了学 KMP 干嘛？）

每一个学过算法竞赛的人，都会就这个名字产生无尽的遐想

SAM

后缀自动机（Suffix Automaton,SAM） 是一个非常强大的数据结构（？），可以在线性时间复杂度下解决大量有关字符串子串的问题。

强烈建议在阅读本段前掌握 ACAM

前置定义

本节包含一些重要的定义，其中包含了 SAM 的精髓，务必熟悉。

为了行文方便，我们做出以下辅助定义：

• 字符串 的长度
• ：字符串 区间构成的子串
• 字符串集合 中，拥有最长长度的字符串
• 字符串集合 中，拥有最短长度的字符串

endpos

对于字符串 的任意子串 ，定义 为 在 中所有出现的位置的末端位置集合。

我知道这段话很绕，所以需要例子辅助理解： ababc，则 ab，因为 ab 在 中匹配的位置分别是 ，因此取这些位置的末端位置 构成集合。

特别的，我们认为空串的 为全体位置。

我们可以得到下面两条显然的关于 的结论（后面会反复用到）：

结论一

如果有子串 满足 ，不妨设 ，那么 一定是 的后缀。

结论二

如果有子串 ，不妨设 ，那么它们的 要么满足 ，要么满足 ，当且仅当 是 后缀时前式成立。

上述两条结论的严格证明比较繁琐，但是结合定义与实例可以轻松理解。

endpos 等价类

我们不妨将所有 相同的子串归为一类，称之为等价类（下文简称类）。更为正式的，我们定义等价类 表示全体满足 的子串构成的集合。

结论三

对于任意类 ，其中包含的字符串满足：长度为 的字符串出现次数均为 ，且短串是长串的真后缀。

换句话说，给定 初始等于 ，一定存在一种构造方式，每次向 的前方添加一个字符直到它等于 ，使得 中的所有字符串都被遍历了一次。

证明：关于后缀的部分由结论二即可得。同时也可以由结论二得到每种长度的字符串只会出现一次。

考虑任意 满足它是 的后缀，那么显然 是它的后缀，那么由结论二可得：。

又由等价类的定义：，因此 必须同时取左右两边的等号。证毕。

link 树

由结论二，对于子串 ，不断地让它向前扩展，它的 集合将会越来越小。

形式化地，设 的 分别为 ，那么一定满足

我们注意到， 中无法取等的位置，对应的意义即为 的收缩，而去掉这些无法取等的位置后用等号连接的部分属于同一个等价类，或更强地说，就是一个等价类（结论三）。

此时如果将等价类视为点，这些不等的关系视为边，那么我们可以得到一张图。关于这张图有以下性质：

• 无环（集合包含的单向性，结论二）
• 连通（任意点都可以通过不断地缩减到空串以到达全集）

因此，这是一棵树。我们称这棵树为 link 树（或 parent 树）。

下图是 abaab 的 link 树。为了方便下一步的内容，我们在图中标注每个结点对应类的最长串：

结论四

对于 link 树上的任意结点 ，均有 成立。换句话说，父亲结点对应等价类的最长串长度 即为子结点对应等价类的最短串。

结论五

link 树中，每个结点的父亲是该结点的断头指针（即所有等价类中的最长真后缀，类似于 ACAM 和 KMP 的 fail 指针）

• 引申：link 树中每个结点最长串是所有儿子对应最长串的最长公共后缀。

上文的定义已经验证了这两个结论。

这里需要说明 link 和 fail 的一个区别在于：fail 针对的是一个确切的字符串，而 link 需要首先取出当前等价类中长度最大的后缀，然后对于这个后缀找到其余等价类中最长长度最大的后缀等价类。

SAM 的构建

SAM 是一个 DFA，其中每个结点都代表了一个等价类，每条边都代表一个转移。（为了方便理解，请把每个结点当成一个压缩字符串，并认为 ACAM 结点里啥字符串都没压缩的）

SAM 能表示字符串的任意子串，即对于任意子串，从起始结点出发，一定能找到一条路径，该路径表示此子串。

为了实现以上功能，设计了下列算法在线构建 SAM：

流程

定义 为上次最后操作的结点， 表示类中最长字符串的长度。

初始时，SAM 只有一个结点 ，。

当插入字符 时：

1. 新建结点 与转移，
2. 从 开始，不断跳父亲结点，沿途添加转移 ，直到找到结点 满足存在转移 停下。如果不存在这样的 ，那么 。
3. • 如果 ，则 。
   • 否则执行复制操作。创建一个新结点 ，从 开始向上遍历将沿途所有转移到 的转移改为转移到 （直到找不到），然后修改 。
4. 令 。

在插入所有字符后，我们从 沿 link 树遍历所有父亲，即为所有终止结点。

正确性证明

FBI Warning：这一节内容极为抽象，也是整篇文章写作过程中耗时最长的部分。如果你是背板选手，请自行跳过这一节。

我知道给谁放上面那个构建方式都头大，所以这一节对于上面的关键步骤都给出详细解释。

首先我们定义一个转移 是连续的当且仅当 ，否则就是不连续的。

新建结点 ，

废话。 好吧还是有用。新建一个结点 是因为新字符的加入带来了一个全新的 ，所以有必要新建一个等价类。

从 开始，不断跳父亲结点，沿途添加转移 ，

回忆 link 树的性质，发现跳 link 树等价于不断切掉前端字符，那么对于树上的这些父亲结点，也理应存在 的转移。

直到找到结点 满足存在转移 停下。

设想一下这种情况：之前的某个后缀已经有了 这个转移。对应到字符串上，也就是之前已经添加过了某个子串，满足最后一个字符为 ，前面的部分是当前的一个后缀。这代表比这个后缀更短的子串 都可以通过 得到了，故无需再向上跳。

如果不存在这样的 ，那么 。

也就是从来没有过上面提到过的那个子串，那么就不存在什么浪费的问题。忽略即可。

如果 ，则 。

接下来我们记 处最长的串为 。

当 时， 一定是 中的所有串的前缀，因此 存在一个后缀满足它是任意转移到 后得到的字符串的前缀（而这个后缀就是 ），可以直接设置 。

否则执行复制操作。创建一个新结点 ，从 开始向上跳 树遍历将沿途所有转移到 的转移改为转移到 （直到找不到），然后修改 （直到不存在）。

当 时，意味着 并非 中所有字符串的前缀（有一部分是 历经其他连续的路径转移得到的），这时我们就需要从原状态中分离出是 后缀的部分，让 只留下非 前缀的字符串（故 ），这样就能把 链接到 上了。这也对应 link 树分裂 集合。

我们希望 拥有 后续所有可能转移到的字符串，因此需要继承 的转移；同时上文提到，操作的本质是分裂 集合，是子树操作，因此不涉及修改，也应当继承。

同时为了做到彻底的分裂，需要重定向 后缀相关的所有到 为 的转移。这一步只要跳到没有 这个转移即可（因为后面不可能有了）。

至于 link 树，我们注意到 包含了新的 ，而 只有旧的 ，对于原有的 的串，如果它包含了新的 ，那么这些新的 已经被移走了。为了访问这一部分的后缀，必须将 连接到 上。

这样，原先的 结点不再涉及关于 的字符串，相关的字符串全部被移动到了 结点上。

时间复杂度分析

谁爱自己研究就研究吧。我累了。

SAM 的性质与应用

紧凑性

SAM 是一个高度压缩的数据结构。可以证明，SAM 的状态数和转移数都为 级别。

证明

上述的构建过程已经证明状态数的数量级。初始有 个状态，而每次操作最多添加 个状态（），故状态数不大于 。这一点也可以通过 link 树证明，因为一棵 个叶结点的多叉树最多有 个结点（二叉树）。

至于转移数，我们首先考虑连续转移数，显然它不可能成无向图意义下的环（否则这两条路径的内容完全一样，完全浪费了），那么这部分不会超过 条边（树）；而考察一条从起始状态到任意终止状态非连续转移，一定对应一个非空真后缀，所以非连续转移不超过 条。

图论性质

从 SAM 的转移角度看，不难看出它是一个 DAG，且正如前文提到的，对于任意子串，从起始结点出发，一定能找到一条路径，该路径表示此子串。

从 link 树角度看，每个结点 表示的字符串数为 （结论三）。

模板

其实 SAM 比很多数据结构都短很多的说。。。

实现时如果字符集很小可以空间换时间，否则只能上 umap（并导致时间翻倍）。

// https://www.luogu.com.cn/problem/P3804

const int SIG = 26;

typedef std::array<int,SIG> sam;

//#define pb push_back

struct SAM{
    private:
        vector<sam> G;
        vi len,siz,fa;
        vector<vi> T;
        int pn,lst;
        int nnode(int cl){
            return G.pb({}),len.pb(0),siz.pb(cl^1),fa.pb(0),++pn;
        }
        int ch(char c){return c-'a';}
    public:
        void ins(char _c){
            int cur=nnode(0),p=lst,c=ch(_c);
            len[cur]=len[lst]+1;
            for(;~p&&!G[p][c];p=fa[p])G[p][c]=cur;
            if(~p){
                int q=G[p][c];
                if(len[q]==len[p]+1)fa[cur]=q;
                else{
                    int cl=nnode(1);
                    G[cl]=G[q];len[cl]=len[p]+1;fa[cl]=fa[q];
                    for(;~p&&G[p][c]==q;p=fa[p])G[p][c]=cl;
                    fa[cur]=fa[q]=cl;
                }
            }
            lst=cur;
        }
        void build(){
            T.resize(G.size()+1);
            for(int i=1;i<G.size();++i)T[fa[i]].push_back(i);
            function<void(int)> dfs=[&](int u){
                for(auto v:T[u])dfs(v),siz[u]+=siz[v];
            };dfs(0);
        }
        SAM(string s):pn(0),G(1),len(1),siz(1),fa(1,-1),lst(0){
            for(auto v:s)ins(v);
            build();
        }
        ll qry(){
            ll ans=0;
            function<void(int)> dfs=[&](int u){
                for(auto v:T[u])dfs(v);
                if(siz[u]!=1)cmax(ans,1ll*len[u]*siz[u]);
            };dfs(0);
            return ans;
        }
};

常见应用

求不同子串个数/总长度（[SDOI2016] 生成魔咒）

可以在 DAG 角度 DP，也可以直接用 link 树结论。

求字典序第 小子串（[TJOI2015] 弦论）

求出每个结点对应字符串个数后按顺序遍历出边即可。

求 endpos 集合大小

显然可以 dfs link 树，答案为子树大小，但是我们认为只有非复制得到的结点拥有大小（可以认为复制得到的结点在 link 树内直接合并了子树）

查找模式串出现次数

在文本串的 SAM 上跑一遍，如果找到了对应的结点，答案就是这个点 endpos 集合的大小。

求 endpos 集合

如果一定要求确切的 endpos 集合，那就上线段树合并吧。

求两个串的最长公共子串

对其中一个串建立 SAM，把另一个串丢到上面跑同时记录当前长度，失配了就跳 link 树父亲（并同步更新当前长度）。

广义 SAM

主播主播，你的 SAM 固然很强，但还是只能处理单个串，有办法让 SAM 跑在 Trie 上吗？

有的兄弟，有的。

我们发现 Trie 上已经有一些现成的连续转移了，并且对于每个结点，它的 也是确定的，所以我们只需要像 ACAM 一样给它暴力跑个广搜，然后照猫画虎地用构建普通 SAM 的方式构建就行了。