[Java][Leetcode simple] 28. 找出字符串中第一个匹配项的下标

暴力匹配I 如果大于m - n则永远不可能有匹配成功的字符串长度太短不够匹配classSolution{publicintstrStr(Stringhaystack,Stringneedle){intmhaystack.length();intnneedle.length();intcnt0;inttmp0;if(mn)return-1;for(inti0;im-n;i){tmpi;cnt0;while(cntn){if(haystack.charAt(tmp)needle.charAt(cnt)){tmp;cnt;}else{break;}}if(cntn){returni;}}return-1;}}KMP算法和暴力匹配相比暴力法一旦匹配失败文本指针要回退、模式串也要从头开始会做很多重复比较效率不高。而 KMP 最大的特点就是文本指针永远不回退只往前走。它的核心思想是利用模式串本身的前后缀重复信息提前预处理出一个 next 数组记录每个位置匹配失败后模式串应该跳到哪里继续比较而不是直接回到 0。这样就避免了重复比较把时间复杂度从暴力的 O (n*m) 优化到了 O(n m)非常稳定高效。classSolution{publicintstrStr(Stringhaystack,Stringneedle){intmhaystack.length();intnneedle.length();if(n0)return0;if(mn)return-1;int[]nextnewint[n];for(inti1,j0;in;i){while(j0needle.charAt(i)!needle.charAt(j)){jnext[j-1];}if(needle.charAt(i)needle.charAt(j)){j;}next[i]j;}for(inti0,j0;im;i){while(j0haystack.charAt(i)!needle.charAt(j)){jnext[j-1];}if(haystack.charAt(i)needle.charAt(j)){j;}if(jn){returni-n1;}}return-1;}}