KMP算法
1. 算法核心
- 利用匹配失败后的信息
- 尽量减少模式串（B）与主串（A）的匹配次数
- 以达到快速匹配的目的
- 通过一个 next 数组，保存模式串（B）中 前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间
2. 如何减少匹配次数
2.1. 字符串的前缀和后缀
# 比如字符串：ababacb
| 前缀集合 | 后缀集合 |
|---|---|
| \(\left \{ a,ab,aba,abab,ababa,ababac \right \}\) | \(\left \{ b,cb,acb,bacb,abacb,babacb \right \}\) |