class Solution {public int strStr(String haystack, String needle) {if (haystack == null || needle == null || needle.length() < 1 || haystack.length() < needle.length()) {return -1;}int[] next=getNext(needle.toCharArray());int i=0; //指向匹配数组的指针   int j=0;//指向被匹配数组的指针int res=-1;while(i<haystack.length()&&j<needle.length()){//如果两个字符相等if(haystack.charAt(i)==needle.charAt(j)){i++;j++;}else if(j>0){//如果还能往左跳j=next[j];}else{//如果到了next数组0位置则说明没有可以匹配的位置了i++;}//子串已经到达最后了，代表父串中已经出现了一次//i和j其实最后都进行了额外的一次++操作}return j == needle.length()? i -j: -1;}public static int[] getNext(char[] str) {if (str.length == 1) {return new int[]{-1};}int[] next = new int[str.length];next[0] = -1;next[1] = 0;// i: next数组的位置int i = 2;// j: 要和next[i-1]比较的位置,最长的可能的公共前缀的位置int j = 0;while (i < next.length) {if (str[i - 1] == str[j]) {next[i++] = ++j;//如j匹配上了则对于此刻i的最大前缀长度加一同时跳到下一个i位置} else if (j > 0) {// 当前跳到j位置的字符，和i-1位置的字符配不上，则j继续向前跳，直到跳到最开始0位置，或者匹配上j = next[j];} else {//j跳到头也没匹配上,i++到下一个位置next[i++] = 0;}}return next;}}