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));}
}

运行结果