-
目录
kmp算法介绍
手动计算next数组
手算next数组
一、介绍
在朴素算法中由于主串需要一步步回溯，增大了开销，最坏情况是主串和模式串对比后发现前面都匹配，只有最后一个字母不匹配。所以下面介绍KMP算法
⬇
⬇
⬇
如果未知？处是g，让i++,j++主串与模式串指针都后移，如图所示
如果未知？处不是g，j=1时候不匹配
j=k时候不匹配，需要一个next数组，记录和模式串里面字符相同的数组下标
二、手算next数组
next数组作用就是当第j个元素发生不匹配时候，next[j]数组应该修改为多少
