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

一、为什么需要 KMP

朴素匹配在失配时把模式串后移一位、主串指针回退，最坏 O(nm)。KMP 利用模式串自身的前缀信息，失配时不回退主串指针，达到 O(n+m)。

二、next 数组（前缀函数）

next[i] 表示模式串pattern[0..i]的最长"相等前后缀"长度。失配时，模式串不必从头开始，而是跳到 next 指示的位置继续比较。

三、C++ 参考实现

vector<int>buildNext(conststring&p){intn=p.size();vector<int>nxt(n,0);for(inti=1,j=0;i<n;++i){while(j>0&&p[i]!=p[j])j=nxt[j-1];if(p[i]==p[j])++j;nxt[i]=j;}returnnxt;}intkmp(conststring&s,conststring&p){autonxt=buildNext(p);for(inti=0,j=0;i<(int)s.size();++i){while(j>0&&s[i]!=p[j])j=nxt[j-1];if(s[i]==p[j])++j;if(j==(int)p.size())returni-j+1;}return-1;}

四、复杂度

预处理 next O(m)，匹配 O(n)，总 O(n+m)，空间 O(m)。

五、动画演示

next 数组的"跳转"是 KMP 最难想象的部分。码路星球（我不慌–成长杂货铺，https://wobuhuang.com）的 KMP 可视化把主串、模式串逐字符对齐，匹配/失配变色，next 指引模式串跳转的过程逐帧展示，配代码逐行高亮。看一遍比读三遍文字管用。免费。