KMP 总结

KMP 总结

tony102

2021 年 08 月 02 日

1058 次浏览

暂无评论

1528字数

总结

先膜楼哥：楼神无敌！

## 不是绝活的东西

你们都会得 KMP 单模式串匹配，就不需要我说了。

## 突破的感受 $\cdot$ 起

KMP 的核心是 `nxt` 数组。`nxt` 数组起到的功能实际是求出一个模式串的**所有前缀的真前缀和真后缀最长的匹配长度。**

这个东西有一些很牛逼的性质，网上大多讲 KMP 的东西都太 naive 了。下面给出一些常用的性质。

1. 快速退回前一个状态的链接。
2. `nxt`的对应关系会构成一棵树。
3. 与 $border$ 联系。

现在来举几个实例。

## 突破的感受 $\cdot$ 承

[[POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435)

简要题意：

> 	求给定字符串所有前缀的最大周期长度之和。
> 	周期的定义为：周期 $Q$ 是 $a$ 的真前缀且 $a$ 是无数个 $Q$ 相连的前缀。

题解：[Sol1](https://tony102.xyz/index.php/2021/08/02/luogu3435-poi2006okr-periods-of-words/)

那么怎么来理解这件事情，你最开始知道 `nxt` 用来每次失配的时候跳一段跟前缀（可能已经跟文本串匹配了一段 $\geq 0$ 的长度），这样每次就可以减少重复的比较。那么 $|S| - nxt_{|S|}$ 相当于往 $|S|$ 一段跟后缀相等的前缀跳。那么那个前缀起始位置之前应该又有一段跟这一样的跳法跳出来的相等的真前后缀。（可能有点绕，但是结合 `nxt` 的实际意义多理解就会明白）

## 突破的感受 $\cdot$ 转

[[NOI2014] 动物园](https://www.luogu.com.cn/problem/P2375)

简要题意：

> 子符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num_i$，求出所有 $num_i$

题解：[Sol2](https://tony102.xyz/index.php/2021/08/02/luogu2375-noi2014-%e5%8a%a8%e7%89%a9%e5%9b%ad/)

由上面的性质知道， $nxt_{|S|}, nxt_{nxt_{|S|}},\dots$ 带来的东西。递推求解即可。

## 突破的感受 $\cdot$ 合

[[POI2005]SZA-Template](https://www.luogu.com.cn/problem/P3426)

一道大火题，做不动

简要题意：

> 你打算在纸上印一串字母。
> 为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。
> 同一个位置的相同字符可以印多次。例如：用 `aba` 这个印章可以完成印制 `ababa` 的工作（中间的 `a` 被印了两次）
> 求最小的印章长度

题解：[Sol3](https://tony102.xyz/index.php/2021/08/02/luogu3426-poi2005sza-template/)