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

暴力匹配

I 如果大于m - n则永远不可能有匹配成功的字符串（长度太短，不够匹配）

classSolution{publicintstrStr(Stringhaystack,Stringneedle){intm=haystack.length();intn=needle.length();intcnt=0;inttmp=0;if(m<n)return-1;for(inti=0;i<=m-n;i++){tmp=i;cnt=0;while(cnt<n){if(haystack.charAt(tmp)==needle.charAt(cnt)){tmp++;cnt++;}else{break;}}if(cnt==n){returni;}}return-1;}}

KMP算法

和暴力匹配相比，暴力法一旦匹配失败，文本指针要回退、模式串也要从头开始，会做很多重复比较，效率不高。
而 KMP 最大的特点就是：文本指针永远不回退，只往前走。
它的核心思想是：利用模式串本身的前后缀重复信息，提前预处理出一个 next 数组，记录每个位置匹配失败后，模式串应该跳到哪里继续比较，而不是直接回到 0。
这样就避免了重复比较，把时间复杂度从暴力的 O (n*m) 优化到了 O(n + m)，非常稳定高效。

classSolution{publicintstrStr(Stringhaystack,Stringneedle){intm=haystack.length();intn=needle.length();if(n==0)return0;if(m<n)return-1;int[]next=newint[n];for(inti=1,j=0;i<n;i++){while(j>0&&needle.charAt(i)!=needle.charAt(j)){j=next[j-1];}if(needle.charAt(i)==needle.charAt(j)){j++;}next[i]=j;}for(inti=0,j=0;i<m;i++){while(j>0&&haystack.charAt(i)!=needle.charAt(j)){j=next[j-1];}if(haystack.charAt(i)==needle.charAt(j)){j++;}if(j==n){returni-n+1;}}return-1;}}