KMP 应用

约定

1. $S,T$通常表示一个字符串。
2. $|S|$表示$S$的长度。
3. $S[i]$表示$S$的第$i$个字符，$S[l,r]$表示$S[l],S[l+1],\cdots,S[r]$构成的子串。
4. 记$\nu(i)$表示$i$的 fail 指针。
5. $S^k$表示$k$个$S$拼在一起。

Border

在进阶之前先铺垫一个基础概念——Border。KMP 的 fail 指针指向的是它的一个最长的 Border。

如果$|S|$被$(|S|-\nu(|S|))$整除，那么$S$就是一个循环串。

对于一个串$S$，如果它的最长 Border 的长度为$L=\nu(|S|)$，且$L\ge \frac{|S|}{2}$，那么$S$就可以写成$AB^k$的形式，且$|B|=|S|-L$，$A$是$B$的后缀。此时最长的 Border 是$AB^{k-1}$。这种情况下的 fail 链是$AB^{k},AB^{k-1},\cdots,AB$。相当于每一次跳一个$B$。

Rank KMP

For sequence$A$and$B$length of$n$, we say$A$similar to$B$, IFF for all$i$and$j$,$A_i<A_j \Leftrightarrow B_i<B_j$.

Now you have two sequence$X$and$Y$, consider the number of consistent subsequence of$X$that similar to$Y$.

$|X|,|Y|\le 10^6$.

与 KMP 算法类似。在扩展的时候，KMP 是判断两个字符是否相等。这里我们则改为判断两个字符在前面的排名是否相同。

主席树即可。

时间复杂度$O(n\log_2n)$。

树上 KMP

给一个 Trie，求每个点到根的路径表示的字符串的最长 Border。

$N,|\Sigma|\le 10^6$。

对于$u$的父节点$p_u$，假设到$p_u$的串表示为$AB^k$，那么每次跳 fail 匹配的是同一个字符$B[1]$。因此如果$B[1]$不匹配就可以直接跳到$AB$了。如果不是$AB^k$就正常跳 fail。这样每次至少减少一半，复杂度$O(n\log_2n)$。

CHO-Hamsters

给出$n$个互不包含的字符串$s_i$，要求你求出一个最短的字符串$S$，使得这$n$个字符串在$S$中总共至少出现$m$次，问$S$最短长度。

$n\le 200,m\le 10^9,\sum |s_i|\le 10^5$。

设$f(i,j)$表示$S$中出现了$i$次这$n$个字符串，末位字符串是$s_j$的$S$的最短长度。

套一个矩阵乘法即可。

时间复杂度$O(n^3\log_2m)$。

Fedya the Potter Strikes Back

给定长度为$n$的字符串$s$和权值数组$w_1,\ldots,w_n$。

定义$s$的⼀个⼦串是好的，当且仅当这个⼦串等于$s$的某个前缀。

⼀个⼦串$s[l,r]$的权值是$w[l,r]$的最⼩值。

对于$s$的每个前缀，求他的所有好的⼦串的权值之和。

$n\le 10^5$。

相当于，对$s[1,i]$求它所有后缀 border 的权值之和。考虑 KMP 算法。从$s[1,i-1]$扩展到$s[1,i]$时：

• 有可能删除一些 border。删除的个数是均摊$O(1)$的。
• 有可能增加一个长度为$1$的 border。
• 其他的$s[1,i-1]$的 border 末尾添加$s_i$，就变成了$s[1,i]$的 border。

那么，想办法$O(1)$找到被删除的 border，然后维护一下权值即可。

对每个 border 维护一下它最远能延伸到的位置即可。

时间复杂度$O(n\log_2n)$。

SZA-Template

给出一个字符串$S$，求一个长度最小的字符串$T$使得$S$可以被$T$印出来。

印的规则是：重叠部分的字符串要一样。

$|S|\le 5\times 10^5$。

求出$S$的 next 数组。

设$f_i$表示前缀$i$的答案。

那么$f_i\in\{i,f_{\text{nex}_i}\}$。因为你要印出$i$，就得先印出$\text{nex}_i$。

而$f_i=f_{\text{nex}_i}$的条件是，存在一个$j$，$f_j=f_{\text{nex}_i}$且$j\ge i-\text{nex}_i$。

时间复杂度$O(n)$。