KMP
单模式串匹配，比较平凡所以不说了，比较有借鉴意义的每次拓展一位和 \(nxt\) 数组能极大减少不合法的匹配，时间复杂度 \(O(|s|+|t|)\)。
引出一个定义，记满足 \(s[1,i]=s[|s|-i+1,|s|]\) 的前缀为字符串 \(s\) 的 \(\mathrm{border}\)，所有的 \(\mathrm{border}\) 构成 \(\mathrm{Border}(s)\) 集合。
失配树
KMP 处理 \(nxt\) 数组时是一个类似 \(nxt_i\leftarrow j\) 的操作，可以看作连边，根节点是 \(0\)，一个前缀对应节点的全部祖先恰好是这个前缀的 \(\mathrm{Border}\) 集合。那么求两个前缀的最长公共 \(\mathrm{border}\) 就是树上 \(\mathrm{LCA}\)，可能需要分是否是祖先关系讨论一下。
KMP 自动机
就是只有一个模式串版本的 AC 自动机，只要从 \(nxt_i\) 构建转移指针就行，目测用处不大。
Z 函数
又叫扩展 KMP。
算法思想
定义 Z 函数 \(z_i=\mathrm{lcp}(s,s[i,|s|])\)，即后缀和原串的 \(\mathrm{lcp}\)。
考虑维护当前最右端的区间 \([l,r]\)，扩展的方法类似 Manacher：
-
若 \(i>r\)，直接暴力拓展；
-
若 \(i\le r\)，那么 \(s[1,r-l+1]=s[l,r]\)，于是 \(s[i-l+1,r-l+1]=s[i,r]\)，那么 \(z_i\ge \min(z_{i-l+1},r-i+1)\)，设为初始值再暴力拓展即可。
复杂度是线性的，证明考虑暴力拓展非 \(O(1)\) 次时 \(r\) 必然增大。
例题
CodeForces-432D Prefixes and suffixes *2000
\(z_i=|s|-i+1\) 的就是 \(\mathrm{border}\)，查询出现次数就是 \(z_i\ge l\) 的位置个数。
Periodicity Lemma
定义 \(p\) 是 \(s\) 的一个周期当且仅当对于 \(1\le i\le |s|-p\)，有 \(s_i=s_{i+p}\)。感性理解就是周期就是一个字符串划分成若干相等的段，最后一段可以是这些段的一个前缀。
Weak Periodicity Lemma：若 \(p,q\) 都是字符串 \(s\) 的周期且 \(p+q\le |s|\)，则 \(\gcd(p,q)\) 也是 \(s\) 的周期。
直观来看 \(p,q\) 导出 \(\gcd(p,q)\) 是类似辗转相除的跳来跳去，存在一个问题：如果将字符串按照两个周期分别补充成无限长，得到的结果可能不相等，例如 \(\texttt{abaababa}\) 如果按 \(\texttt{abaab}\) 和 \(\texttt{abaabab}\) 补充肯定是不相等的，那么跳来跳去就可能出错，所以有一个长度的限制。
弱周期引理的证明比较简单，考虑归纳，规定 \(p\le q\)，假设已经证明对于任意 \(x<p,y<q\) 都是成立的，而 \(p=1\) 时显然也成立。由于 \(p+q\le |s|\) 且 \(p\le q\)，可以将 \(1\le i\le |s|\) 划分成 \(i\le |s|-q\) 和 \(i>|s|-q\) 两部分。对于前者，\(i+q\) 与 \(i+q-p\) 都在 \([1,|s|]\) 范围内，于是 \(s_i=s_{i+q-p}\)；对于后者，实际考虑 \(p\le |s|-q<i\le |s|-(q-p)\)，\(i-p\) 与 \(i-p+q\) 都在范围内，于是 \(s_i=s_{i-p+q}\)，\(q-p\) 就是 \(s\) 的一个周期，而根据归纳 \(\gcd(q-p,p)=\gcd(p,q)\) 也是 \(s\) 的一个周期。
Periodicity Lemma：若 \(p,q\) 都是字符串 \(s\) 的周期且 \(p+q-\gcd(p,q)\le |s|\)，则 \(\gcd(p,q)\) 也是 \(s\) 的周期。
有一个生成函数证明，感觉很有趣。记 \(P(x),Q(x)\) 分别为长度为 \(p,q\) 的周期，\(S_p(x),S_q(x)\) 分别为按照周期补充的无限长串，那么满足：
\[S_p(x)=\dfrac{P(x)}{1-x^p}\equiv S(x)\pmod {x^{|s|}} \]\[S_q(x)=\dfrac{Q(x)}{1-x^q}\equiv S(x)\pmod {x^{|s|}} \]于是可以得到：
\[S_p(x)-S_q(x)=\dfrac{P(x)}{1-x^p}-\dfrac{Q(x)}{1-x^q}=\dfrac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}\left(\dfrac{P(x)(1-x^q)}{1-x^{\gcd(p,q)}}-\dfrac{Q(x)(1-x^p)}{1-x^{\gcd(p,q)}}\right) \]把后面的东西记作 \(F(x)\)，观察可知 \(\deg F(x)<p+q-\gcd(p,q)\le |s|\)，而 \(S_p(x)-S_q(x)\equiv 0\pmod {x^{|s|}}\)，所以 \(F(x)\equiv 0 \pmod{x^{|s|}}\)，根据其度数知 \(F(x)=0\)，所以 \(S_p(x)=S_q(x)\)，不需要截取，所以后面就能按照辗转相除证明了。
Border Series
参考资料
Z 函数
周期引理
-
课件 - 张铠麒 Cage