本篇介绍几种常见字符串匹配算法，分别为

• BF算法（Brute Force，也就是暴力算法）
• KMP算法（Knuth-Morria-Pratt算法,其实就是这三个人共同提出的）
• BM算法（Boyer-Moore）
• Sunday算法（由Daniel M.Sunday在1990年提出）

Brute Force算法

也就是我们所谓的暴力算法。

顾名思义，假如有两个字符串：

• M（主串/被比较/m个字符）
• N（模式串/拿去比较/n个字符）

如图所示：
从左向右比较，开始时，若相同则M往后一位，N往后一位继续比，若不相同则M从第二位开始，N从第一位开始比较，依此类推。

最坏时N的比较要循环m次，且每一位都要被比，因此最坏时间复杂度为O(n*m)

KMP算法

KMP算法用文字描述相当的不直观，需要不停地变化，因此这里我直接搬上我兄弟Carl的视频，讲的非常清楚，大家也可以关注一波。

---

理论篇

<iframe allowfullscreen="allowfullscreen" frameborder="0" height="600px" scrolling="no" src="https://player.bilibili.com/player.html?aid=712030093&bvid=BV1PD4y1o7nd&cid=234332326&page=1&as_wide=1&high_quality=1&danmaku=0" width="100%"></iframe>

---

next函数构造篇

<iframe allowfullscreen="allowfullscreen" frameborder="0" height="600px" scrolling="no" src="https://player.bilibili.com/player.html?aid=457239548&bvid=BV1M5411j7Xx&cid=237602669&page=1&as_wide=1&high_quality=1&danmaku=0" width="100%"></iframe>

BM算法