28. 实现 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

方法一：暴力求解

方法二：KMP算法

使用KMP算法的关键在于得到next数组，且我们让数组下标从0开始。
求解next数组的关键在于：

1 next[j+1]的最大值为next[j]+1
2 如果Pj ≠ Pnext[j]，那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]

具体求解next数组思想：https://www.bilibili.com/video/BV16X4y137qw/

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0){  //当needle为空字符串时返回0
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next,needle);
        for(int i = 0;i<next.length;i++){
            System.out.println(next[i]);
        }
        int i = 0,j = 0;
        while(i < haystack.length()&&j < needle.length()){
            if(j == -1||haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if(j >= needle.length()){
            return i-needle.length();
        }else{
            return -1;
        }
    }
    /**
    求解next数组的关键在于
        1 next[j+1]的最大值为next[j]+1
        2 如果Pj ≠ Pnext[j]，那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]
     */
    public void getNext(int[] next,String needle){
        int j;  //要比较的字符的下标
        int i = 1;  //待确定的next数组元素的下标
        next[0] = -1;
        j = i-1;
        while(i<needle.length()){
            if(next[j] == -1){
                next[i++] = next[j]+1;
                j = i-1;
            }else if(needle.charAt(i-1)==needle.charAt(next[j])){
                next[i++] = next[j]+1;
                j = i-1;
            }else{
                j = next[j];
            }
        }
    }
}