数据结构——KMP 字符串匹配算法：next 数组计算与优化

KMP 是 408 必考算法，这篇把 next 数组手算、代码实现、优化方法讲透。

一、KMP 核心思想

暴力匹配：匹配失败后主串回溯，浪费已匹配的信息 KMP：主串不回溯，利用 next 数组跳过不必要的比较

二、next 数组手算

模式串 "abaabcac" j=0：next[0] = -1 j=1：T[0:0]="" → 无子串 → next[1]=0 j=2：T[0:1]="ab" → 前缀{"a"} 后缀{"b"} → 无相等 → next[2]=0 j=3：T[0:2]="aba" → "a"长度1 → next[3]=1 j=4：T[0:3]="abaa" → "a"长度1 → next[4]=1 j=5：T[0:4]="abaab" → "ab"长度2 → next[5]=2 next = [-1, 0, 0, 1, 1, 2]

三、代码实现

publicstaticint[]getNext(Stringpattern){intm=pattern.length();int[]next=newint[m];next[0]=-1;inti=0,j=-1;while(i<m-1){if(j==-1||pattern.charAt(i)==pattern.charAt(j)){i++;j++;next[i]=j;}else{j=next[j];}}returnnext;}publicstaticintkmp(Stringtext,Stringpattern){intn=text.length(),m=pattern.length();int[]next=getNext(pattern);inti=0,j=0;while(i<n&&j<m){if(j==-1||text.charAt(i)==pattern.charAt(j)){i++;j++;}else{j=next[j];}}returnj==m?i-j:-1;}

四、nextval 优化

publicstaticint[]getNextVal(Stringpattern){intm=pattern.length();int[]nextval=newint[m];nextval[0]=-1;inti=0,j=-1;while(i<m-1){if(j==-1||pattern.charAt(i)==pattern.charAt(j)){i++;j++;nextval[i]=pattern.charAt(i)!=pattern.charAt(j)?j:nextval[j];}else{j=nextval[j];}}returnnextval;}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！