KMP算法及改进（C++）

原视频up主：@木子喵neko

视频地址：https://www.bilibili.com/video/BV1234y1y7pm

自己随手写了一个（躺平）：

运行结果如下：

其实还可以进行进一步优化， 进一步利用失配时可以获取到的信息：

当失配时可以知道a[i] != b[j]。

而next[i]表示的是在b串中，第i位失配后需要将j位移到的下一个位置， 即加下来要比较a[i]和b[next[j]]。如果此时b[j] == b[next[j]]， 接下来的比较其实也是多余的。因此对kmp_next函数可以进行一下改进：

运行结果如下：