KMP 算法详解：next 数组原理 + C++ 实现 + 过程图解

KMP 算法详解next 数组原理 C 实现 过程图解一、为什么需要 KMP二、next 数组前缀函数三、C 参考实现四、复杂度五、动画演示一、为什么需要 KMP朴素匹配在失配时把模式串后移一位、主串指针回退最坏 O(nm)。KMP 利用模式串自身的前缀信息失配时不回退主串指针达到 O(nm)。二、next 数组前缀函数next[i] 表示模式串pattern[0..i]的最长相等前后缀长度。失配时模式串不必从头开始而是跳到 next 指示的位置继续比较。三、C 参考实现vectorintbuildNext(conststringp){intnp.size();vectorintnxt(n,0);for(inti1,j0;in;i){while(j0p[i]!p[j])jnxt[j-1];if(p[i]p[j])j;nxt[i]j;}returnnxt;}intkmp(conststrings,conststringp){autonxtbuildNext(p);for(inti0,j0;i(int)s.size();i){while(j0s[i]!p[j])jnxt[j-1];if(s[i]p[j])j;if(j(int)p.size())returni-j1;}return-1;}四、复杂度预处理 next O(m)匹配 O(n)总 O(nm)空间 O(m)。五、动画演示next 数组的跳转是 KMP 最难想象的部分。码路星球我不慌–成长杂货铺https://wobuhuang.com的 KMP 可视化把主串、模式串逐字符对齐匹配/失配变色next 指引模式串跳转的过程逐帧展示配代码逐行高亮。看一遍比读三遍文字管用。免费。