基础字符串 学习笔记

本文主要整理了： - 字符串的基础概念与定义 - 基础 Border 理论 - KMP 算法 有些贺自 [ix35 的博客](https://www.luogu.com.cn/blog/ix-35/noi-yi-lun-fu-xi-ii-zi-fu-chuan)。限于篇幅和本文偏应用的目的，会略去大多数性质的证明。 ## 概念与定义 （只会记录一些我不太会的定义） #### 基础概念 - 字符集 $\Sigma$ 生成的**所有**字符串的集合为 $\Sigma^*$。可以看到，若 $\Sigma\ne \varnothing$，则 $\Sigma^*$ 为无穷集。 - 定义**空串**为长度为 $0$ 的串，记为 $\epsilon$。$\epsilon$ 是任意群 $(\Sigma^*,+)$ 中唯一的零元。（$+$ 表示拼接操作） - 拼接操作可被记为 $C=A+B$，也可写作 $C=AB$。 - 记一个字符串 $S$ 的**反串**为 $S^R$，那么 $S$ 为**回文串**当且仅当 $S=S^R$。注意：$\epsilon$ 也是回文串。 #### 周期结构 - 定义 $x$ 是 $S$ 的**周期（Period）**，当且仅当 $x\le |S|$ 且 $\forall i\in[1,|S|-x],\ S_i=S_{i+x}$。 若 $x$ 整除 $|S|$，则称 $x$ 是 $S$ 的一个**整周期**。 - 定义 $T$ 是 $S$ 的 **Border**（缩写为 Bd），当且仅当 $T$ 同时是 $S$ 的**真前缀**和**真后缀**。 同时也称 $|T|$ 是 $S$ 的 Border。 容易看出 $|S|$ 是任意字符串 $S$ 的**平凡周期**，$0$ 或 $\epsilon$ 是其**平凡 Border**。 ## Border 理论的基本性质 - **性质：$p$ 是 $S$ 的周期，当且仅当 $|S|-p$ 是 $S$ 的 Border.** 十分显然，证明略。 不过这确实是一条非常有用的结论，借助它可以用 KMP 在 $\mathcal O(n)$ 内求出字符串的所有周期。 - **弱周期引理（Weak Periodicity Lemma）：若 $p,q$ 是 $S$ 的周期，且 $p+q\le |S|$，则 $\gcd(p,q)$ 也是 $S$ 的一个周期。** > 证明：观察有 $\gcd(p,q)$ 的形式，猜想可以用辗转相除的思路证明。 > > 当 $p=q$ 时显然成立，因此不妨设 $p>q$，我们证明 $p-q$ 也是 $S$ 的一个周期。 > > $\forall x\in[p+1,p+q]$，有 $S_x=S_{x-p}=S_{x-q}$。因此有 $\forall x\in [1,q],\ S_x=S_{x+p-q}$。 > > 而 $\forall x>q,\ S_x=S_{x-q}=S_{x+p-q}$，可知 $p-q$ 是 $S$ 的一个周期，再借用辗转相除法得 $\gcd(p,q)$ 是 $|S|$ 的周期。 实际上这个引理可以进一步加强： - **周期引理（Periodicity Lemma）：若 $p,q$ 是 $S$ 的周期，且 $p+q-\gcd(p,q)\le |S|$，则 $\gcd(p,q)$ 也是 $S$ 的一个周期。** 取 $S=\texttt{abacaba}$，$p=6,q=4$。则 $\gcd(6,4)=2$ 不是 $S$ 的一个循环节。 同时我们注意到 $p+q-\gcd(p,q)=8=|S|+1$，因此周期引理的上界是紧的。 具体证明用到生成函数，就不管了。 - **长字符串的匹配定理：若 $2|S|\geq|T|$，则 $S$ 在 $T$ 中的匹配位置必为等差序列。** > 证明：易见 $S$ 在 $T$ 中的多个匹配必然有重叠的部分。 > > 考虑去掉 $T$ 中没有被覆盖的字符，然后考虑反证。 > > 设有三个最近的匹配相距分别 $p,q(p\ne q)$，我们发现这三个匹配覆盖的字符串一定有周期 $p,q$。 > > 于是便可以利用弱周期引理证明 $\gcd(p,q)$ 也是它们的周期，于是便可以构造出它们中间的一组匹配，推翻假设。 - **短周期结构：字符串 $S$ 有不超过 $\dfrac{|S|}{2}$ 的周期 $y$，当且仅当 $y$ 是其最短周期 $x$ 的倍数。** > 证明：充分性是显然的，下证必要性。 > > 若 $x>\dfrac{|S|}{2}$ 或 $y=x$，则结论已成立。下面假设 $x\le \dfrac{|S|}{2},y>x$，对任意 $S$ 的周期 $y\le \dfrac{|S|}{2}$，即有 $x+y\le|S|$。 > > 因此 $y-x$ 也是 $|S|$ 的周期。若 $x\nmid y$，设 $y\equiv r\pmod{x}$，则可以找出一个周期 $r<x$，构成矛盾。 > > 故总有 $x\mid y$ 成立。 - **长 Border 结构：字符串 $S$ 的所有不小于 $\dfrac{S}{2}$ 的 Border 构成等差数列，且如果排序后延申这个数列，下一项就是 $|S|$。** > 证明：由短周期结构的结论，字符串 $S$ 的所有不超过 $\dfrac{|S|}{2}$ 的周期成等差数列。 > > 由上面的性质可知长 Border 也成一个这样的等差数列。 简单的说，以 $\dfrac{|S|}{2}$ 为界，**短周期**和**长 Border** 分别成等差数列。 - **字符串的周期/Border 结构：字符串 $S$ 的所有周期或 Border 形成了 $\mathcal O(\log n)$ 个值域不交的等差数列**。 > 证明：有一个结论是，**若 $p$ 和 $q\ (p<q)$ 都是 $S$ 的 Border，则 $p$ 也是 $S[1\cdots q]$ 的 Border**。 > > - 设 $S$ 的最长 Border 长度为 $b_0$，有 $b_0<|S|$，且： > - 长度在 $[\dfrac{b_0}{2},b_0]$ 之间的 Border 都是 $S[1\cdots b_0]$ 的 Border，成一个等差数列； > > - 设最长的小于 $\dfrac{b_0}{2}$ 的 Border 长度为 $b_1$，有： > - 长度在 $[\dfrac{b_1}{2},b_1]$ 之间的 Border 都是 $S[1\cdots b_1]$ 的 Border，成一个等差数列； > > 此时我们已证明长度在 $[\dfrac{|S|}{2^2},|S|]$ 之间的 Border 成至多 $2$ 个等差数列，同上简单归纳可知结论成立。 这里刻画了大于 $\dfrac{|S|}{2}$ 的周期 / 小于 $\dfrac{|S|}{2}$ 的 Border 的性质。 - 例题：[P4156 [WC2016]论战捆竹竿](https://www.luogu.com.cn/problem/P4156) [这里](https://www.luogu.com.cn/paste/t00cpyq7)是一个错解，没有考虑到**短周期结构只对不大于 $\dfrac{|S|}{2}$ 的周期适用**。 那么还怎么做呢？可以考虑**同余最短路**，跑出来再进行转移，具体看题解。 可以发现，**求一个数列的线性组合一般使用同余最短路**。 （好像写歪了）总复杂度 $\mathcal O(Tn\log n)$。 一直调不出！！！！！！ ## 前缀函数与 KMP 算法 Knuth-Morris-Pratt 算法是一种能在 $\mathcal O(n)$ 内求出字符串 $S$ 的前缀函数 / 将另一个字符串 $T$ 和 $S$ 进行匹配的算法。 定义：$S$ 的**前缀函数（Prefix function）**$\pi(i)$ 表示 $S[1\cdots i]$ 的**最长 Border 长度**。 为引出 KMP 算法，给出如下结论： - **性质：设 $S[1\cdots i]$ 的所有 Border 长度所形成的集合为 $\mathrm{Bd}_i$，则有：** $$ \mathrm{Bd}_i=\begin{cases} \{0\} & \pi(i)=0\\ \mathrm{Bd}_{\pi(i)}\cup{\pi(i)} & \pi(i)>0 \end{cases} $$ > 证明：易证 $\complement_{\mathrm{Bd}_{i}}\{0\}\subseteq\mathrm{Bd}_{\pi(i)}$，再由反证法可证明 $\mathrm{Bd}_{\pi(i)}\subseteq\mathrm{Bd}_i$。详细证明略去。 现在来研究如何求出 $\pi(i)$。 由于复杂度要求是 $\mathcal O(n)$ 的，因此我们考虑从 $\pi(i-1)$ 导出 $\pi(i)$。 我们发现，由前缀函数的定义，$\pi(i)\le\pi(i-1)+1$，否则 $\pi(i)-1$ 一定是 $\pi(i-1)$ 的一个更优的解。 同理也可以得到 $\pi(i)-1\in \mathrm{Bd}_{i-1}$，那么我们从大到小枚举 $\mathrm{Bd_{i-1}}$ 中的数 $j$，直到 $S_{j+1}=S_i$（可以扩展一位）或 $j=0$（匹配失败）。 一般在代码中把 $\pi(i)$ 写作 $\texttt{next}$ 数组或 $\texttt{fail}$ 数组，代码如下：（注意要从 $i=2$ 开始枚举） ```c++ int j=0; Next[1]=0; fo(i,2,n) { while( j>0 && s[j+1]!=s[i] ) j=Next[j]; if(s[j+1]==s[i]) j++; Next[i]=j; } ``` 然后处理如何在 $S$ 中匹配 $T$，我们发现这个过程和上面是类似的。 下面我们来分析它的复杂度。 可以看出，第 3 行的 `while` 循环每执行一次至少会使 $j$ 的值减小 $1$，而 $j$ 总共被增加了不超过 $n$ 次。 因此第 3 行的 `while` 循环至多会执行不超过 $\mathcal O(n)$ 次，总复杂度是 $\mathcal O(n)$ 的。 - 例题：[P3375 【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375) 直接把上面的东西写出来： ```c++ #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define il inline const int N=1000010; int n,m,Next[N]; char s[N],t[N]; int main() { scanf("%s",t+1), m=strlen(t+1); scanf("%s",s+1), n=strlen(s+1); int j=0; Next[1]=0; fo(i,2,n) { while( j>0 && s[j+1]!=s[i] ) j=Next[j]; if(s[j+1]==s[i]) j++; Next[i]=j; } j=0; fo(i,1,m) { while( j>0 && s[j+1]!=t[i]) j=Next[j]; if(s[j+1]==t[i]) j++; if(j==n) printf("%d\n",i-j+1); } fo(i,1,n) printf("%d ",Next[i]); puts(""); return 0; } ``` 实际上，由于 NOI 大纲中不高于提高级的字符串算法只有 KMP，因此碰到联赛范围以内的字符串题不会做时，一般都是先跑一遍 KMP 求出 $\pi(i)$ 然后找性质。 ## 例题 感觉有点偏（ - [CF1200E Compress Words](https://www.luogu.com.cn/problem/CF1200E) 维护一个答案字符串，每次都对需要加入的字符串算出 $\pi(i)$，然后在答案字符串上进行正序的匹配。 具体做法可参考代码。[Code](https://www.luogu.com.cn/record/59231022) - [P3193 [HNOI2008]GT考试](https://www.luogu.com.cn/problem/P3193) 看到 $m\le20$ 而 $n\le 10^9$ 十分诡异，考虑矩乘。 我们考虑一个 DP，记 $dp_{i,j}$ 为当前到第 $i$ 位，还没有不合法子串但当前有 $j$ 位匹配上了。 然后跑一遍 KMP 处理矩阵的系数，就可以愉快地矩阵快速幂了。 [Code](https://www.luogu.com.cn/record/59320064) ## 失配树 给出**失配树（Border Tree）**的定义： 对于每个 $i$，我们连边 $i\to\pi(i)$，便可得到一棵**以 $0$ 为根的树**，不难发现这棵树满足小根堆性质。 那么，一个前缀 $S[1\cdots i]$ 的所有 Border 就是 $i$ 在树上的所有祖先。 失配树有什么用呢？它可以将一个字符串问题转化为我们熟悉的树论问题。 - **性质：失配树中的每个点的编号都比其父结点大。** 这是显然的。这样我们可以给出这棵树的一个拓扑序为 $\{n,n-1,\cdots,1\}$。 这样我们在失配树上 DP 时就不用写 DFS 了 ### 例题 - 模板：[P5829 【模板】失配树](https://www.luogu.com.cn/problem/P5829) > 给出一个字符串 $S$，求 $S$ 的两个长度分别为 $n$ 和 $m$ 的前缀的最长公共 Border 长度。 不难发现，只要建出失配树，$\operatorname{LCA}(n,m)$ 就是答案。 但是，真的是 $\operatorname{LCA}(n,m)$ 吗？我们发现，若 $n,m$ 中有一个是另一个的祖先，则答案为它的父亲。 特判即可。[Code](https://www.luogu.com.cn/problem/P5829) - 例题：[P2375 [NOI2014] 动物园](https://www.luogu.com.cn/problem/P2375) 这题大致是让我们对每个 $i$ 求出 $\mathrm{Bd}_i$ 中 $\le \dfrac{i}{2}$ 的元素个数。 暴力肯定要超时，貌似可以倍增，但算算复杂度发现它没有前途。 我们考虑从树上入手。 一种做法是 DFS 一遍树然后移指针，但是移指针很费时间，能卡到 $\mathcal \Theta(n^2)$，参见 ZCETHAN 被 hack 的[记录](https://uoj.ac/submission/513633)。 我的做法是先正着算出每个点的深度，再从大到小枚举 $i$，然后像并查集那样合并结点。由于每个点只会被合并一次，所以复杂度是 $\mathcal O(n)$ 的。 [Code](https://www.luogu.com.cn/record/59279497) 题解区有一种做法是算出深度后模拟一遍 KMP 过程： ```c++ fo(i,1,n) { while( j>0 && s[j+1]!=s[i])) j=Next[j]; if(s[j+1]==s[i]) j++; while(2*j>i) j=fail[j]; res=res*(ll)(ans[j]+1)%P; } ``` 这个做法主要考虑到**如果一个 Border 在某个位置不合法，那么由它扩展的都不会合法**。 - [P3426 [POI2005]SZA-Template](https://www.luogu.com.cn/problem/P3426) 非常神仙的一道题。 我们考虑一个 DP，设 $dp_i$ 表示要印出 $S[1\cdots i]$ 至少需要多长的印章，不难发现 $dp_1=1$，且： $$ \forall i\in [1,|S|],\ dp_i\in \mathrm{Bd}_i\cup \{i\} $$ 也就是说，$dp_i$ 在失配树中 $i$ 和 $\mathrm{anc}(i)$ 中取值，若 $\pi(i)=0$，则 $dp_i=i$。 若 $dp_i<i$，则 $dp_i\le \pi(i)$，$S[1\cdots dp_i]$ 能覆盖 $S[1\cdots\pi(i)]$。 因此有 $dp_i\geq dp_{\pi(i)}$，$dp$ 数组在失配树的一条链上呈一个单调性。 然后就不会了，看了[这篇题解](https://www.luogu.com.cn/blog/wtgrz/solution-p3426)，然后就发现自己是 sb。 因为如果 $dp_i$ 取到 $(dp_{\pi(i)},\pi(i)]$ 之间的数，那么因为它的某个 Border 一定是 $dp_{\pi(i)}$，且由 $dp_{\pi(i)}$ 的性质，$dp_{\pi(i)}$ 一定能生成这个字符串。 因此它能生成的所有串一定是 $dp_{\pi(i)}$ 所生成的子集。换句话说，取答案为 $(dp_{\pi(i)},\pi(i)]$ 之间的数一定不比 $dp_{\pi(i)}$ 优。 考虑什么时候我们被迫取 $dp_i=i$，我们发现当且仅当 $S[1\cdots \pi(i)]$ 无法覆盖 $S[1\cdots i]$ 时才取 $dp_i=i$。 这可以用一个桶维护，代码见下。 ```c++ #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define il inline const int N=500010; int n; char s[N]; int Next[N],dp[N],pre[N]; int main() { scanf("%s",s+1), n=strlen(s+1); int j=0; Next[1]=0; fo(i,2,n) { while( j>0 && s[j+1]!=s[i] ) j=Next[j]; if(s[j+1]==s[i]) j++; Next[i]=j; } dp[1]=1, pre[1]=1; fo(i,2,n) { if( pre[dp[Next[i]]]+dp[Next[i]] >= i) dp[i]=dp[Next[i]]; else dp[i]=i; pre[dp[i]]=i; } printf("%d\n",dp[n]); return 0; } ```