本文主要是介绍Leetcode面试经典150题-28.找出字符串第一个匹配项的下标，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法都在代码里，不懂就留言或者私信，比第一题稍微难点
用KMP解这个题简直就像大炮打蚂蚁，但是没办法，现在都是这么卷
package dataStructure.bigFactory;public class _28Strstr {public static int strStr(String s1, String s2) {/**健壮性判断*/if(s1 == null || s2 == null) {return -1;}/**你比我还大，我怎么可能在内部找到你*/if(s2.length() > s1.length()) {return -1;}/**都转成字符数组*/char[] sArr1 = s1.toCharArray();char[] sArr2 = s2.toCharArray();/**获取s2的next数组，整个kmp的核心*/int[] next = generateNextArr(sArr2);/**pos1和pos2分别代表s1和s2正在匹配的位置*/int pos1 = 0;int pos2 = 0;/**下面开始匹配的过程*/while(pos1 < sArr1.length && pos2 < sArr2.length) {if(sArr1[pos1] == sArr2[pos2]) {pos1 ++;pos2 ++;} else if(next[pos2] != -1) {/**如果还可以回跳，就回跳(不是0位置)*/pos2 = next[pos2];} else {/**不能回跳的时候，表示0～pos1区间找不到这样的开头*/pos1 ++;/**这个时候pos2肯定是0*/}}/**出循环有两种可能：1.pos1越界了 2.pos2越界了* 如果pos1越界代表死都没匹配上，返回-1，pos2越界表示匹配结束找到了可以返回对应的开始位置* 我们把现在的pos1往前sArr2.length个就是开始的位置（因为pos1当前是匹配位置的下一个）*/return pos2 == sArr2.length? pos1-sArr2.length : -1;}public static int[] generateNextArr(char[] s2) {if(s2.length == 1) {return new int[]{-1};}
/**next数组代表最长的前缀和后缀可以匹配的长度，前缀和后缀都不包含整个字符串*/int[] next = new int[s2.length];/**这个写死，是我们的规定*/next[0] = -1;next[1] = 0;/**aabaaac*/int index = 2;//这个变量有两个含义：1.从0到index-1这个子数组前缀串和后缀串的最大匹配长度//2.计算index的next的值的时候和index-1位置比较的位置int nextPosOfPrevious = 0;while(index < s2.length) {if(s2[index - 1] == s2[nextPosOfPrevious]) {next[index ++] = ++nextPosOfPrevious;} else if(next[nextPosOfPrevious] >= 0) {nextPosOfPrevious = next[nextPosOfPrevious];} else {next[index ++] = 0;}}return next;}public static void main(String[] args) {String s1 = "aabcca";String s2 = "abc";System.out.println(strStr(s1,s2));}
}
运行结果
最近确实没时间查到底是字节第几高的题了，稍后补充吧
也许KMP这个大家没太懂，过几天有空了我专门写一下KMP的文章解释一下，到时候还以这个为例子
这篇关于Leetcode面试经典150题-28.找出字符串第一个匹配项的下标的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
