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

KMP 是 408 必考算法这篇把 next 数组手算、代码实现、优化方法讲透。一、KMP 核心思想暴力匹配匹配失败后主串回溯浪费已匹配的信息 KMP主串不回溯利用 next 数组跳过不必要的比较二、next 数组手算模式串 abaabcac j0next[0] -1 j1T[0:0] → 无子串 → next[1]0 j2T[0:1]ab → 前缀{a} 后缀{b} → 无相等 → next[2]0 j3T[0:2]aba → a长度1 → next[3]1 j4T[0:3]abaa → a长度1 → next[4]1 j5T[0:4]abaab → ab长度2 → next[5]2 next [-1, 0, 0, 1, 1, 2]三、代码实现publicstaticint[]getNext(Stringpattern){intmpattern.length();int[]nextnewint[m];next[0]-1;inti0,j-1;while(im-1){if(j-1||pattern.charAt(i)pattern.charAt(j)){i;j;next[i]j;}else{jnext[j];}}returnnext;}publicstaticintkmp(Stringtext,Stringpattern){intntext.length(),mpattern.length();int[]nextgetNext(pattern);inti0,j0;while(injm){if(j-1||text.charAt(i)pattern.charAt(j)){i;j;}else{jnext[j];}}returnjm?i-j:-1;}四、nextval 优化publicstaticint[]getNextVal(Stringpattern){intmpattern.length();int[]nextvalnewint[m];nextval[0]-1;inti0,j-1;while(im-1){if(j-1||pattern.charAt(i)pattern.charAt(j)){i;j;nextval[i]pattern.charAt(i)!pattern.charAt(j)?j:nextval[j];}else{jnextval[j];}}returnnextval;} 觉得有用的话点赞 关注【张老师技术栈】吧