KMP 算法：next 数组分析

张开发
• 2026/4/8 1:11:39 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

KMP 算法：next 数组分析
本人大二学生一名在学习KMP算法时有感而发一、算法核心KMP 算法用于字符串模式匹配核心是利用 next 数组跳过不必要的比较时间复杂度O(nm)远优于暴力匹配的 O (n*m)。二、next 数组原理最长相等前后缀next 数组记录模式串每个位置的最长相等前缀后缀长度匹配失败时快速回退避免从头比较。三、个人对next数组求值地理解求next数组的下标对应的位置核心jnext[j-1]next数组长度为字串长度第一个函数getNext(),构建next数组初始j0;next[0]0假设数组p为ABABC第一个next[0]0;//公式化打法第二个为Bp[1]和p[0](此时j0)比较显而易见A!B所以j依旧为0next[1]0第三个为A,p[2]和p[0](j0)比较可以发现AA,字符相等j,此时j1,next[2]1第四个为B,因为此时j1,所以p[3]和p[1]j1比较,p[3]p[1](BB),字符相等j,此时j2,next[3]2第四个为C,此时j2p[4]和p[2]比较,很明显(C!A),所以j--,j1,此时将next[j-1]赋给j也就是next[1]0.next数组ABABCNext[j]00120j00120四将字符串和字串进行匹配#includestdio.h#includestring.hvoid getNext(const char *pat,int *next){int lenstrlen(pat);next[0]0;int j0;for(int i1;ilen;i){while(j0pat[i]!pat[j]){jnext[j-1];}if(pat[i]pat[j]){j;}next[i]j;}}int KMP(const char *txt,const char*pat){int nstrlen(txt);//主串int mstrlen(pat);//子串 //求next长度if(m0)return 0;int next[m];getNext(pat,next);int i0;int j0;while(in){if(txt[i]pat[j]){i;j;}if(jm)//字符串完全匹配返回首字符{return i-j;}else if(intxt[i]!pat[j])//如果当前字符和字串的不匹配{if(j!0){jnext[j-1];}else{i;}}}return -1;//没找到}int main(){char text[]ABABABC;char pattern[]ABABC;int posKMP(text,pattern);if(pos!-1){printf(匹配成功起始下标%d\n,pos);}else{printf(未找到匹配\n);}return 0;}

更多文章