给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。如果needle=""，那么返回0。

解题思路：KMP
(1) 简单的解法：设立双指针，一个指向主串【i】，一个指向模式串【j】。每次遇到不匹配时，就回溯，移动j从头开始匹配。时间复杂度：假定主串s的长度为n，模式串p的长度为m，O(nm)*。

class Solution {
    public int strStr(String haystack, String needle) {
        int i = 0;
        int j = 0;
        int n = 0;
        while(true){
            // 找到了最先出现的needle子串
            if(n >= needle.length()) return i;
            // 说明本次寻找不匹配，在刚开始进入时,无需匹配。
            else if(j > 0){
                j = j - n + 1;
                n = 0;
            }
            // 不匹配时，找到第一个能与之匹配的下标
            while(j < haystack.length() && n < needle.length() && haystack.charAt(j) != needle.charAt(n)) j++;
            if(j >= haystack.length()) break;
            i = j;
            // 匹配时
            while(j < haystack.length() && n < needle.length() && haystack.charAt(j) == needle.charAt(n)){
                j++;
                n++;
            }
        }
        return -1;
    }
}

(2) 使用KMP，存下之前遍历的信息（next数组）。⭐ 时间复杂度：假定主串s的长度为n，模式串p的长度为m，O(n + m)。
指针 i 可以不用回溯，同时也避免指针 j 从头再去做匹配。
● KMP详解：0. 字符串理论知识 - 简书 (jianshu.com)

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        next[0] = 0;
        createNext(next, needle);
        int i = 0;
        int j = 0;
        while(i < haystack.length()){
            while(j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];
            if(haystack.charAt(i) == needle.charAt(j)) j++;
            i++;
            if(j >= needle.length()) return i - j;
        }
        return -1;
    }
    public void createNext(int[] next, String p){
        int i = 1;
        int j = 0;
        while(i < next.length){
            // 不匹配时，回退指针j，直到匹配或j = 0
            while(j > 0 && p.charAt(j) != p.charAt(i)){
                j = next[j - 1];
            }
            // 此时查看是否能匹配上
            if(p.charAt(j) == p.charAt(i)){
                j++;
            }
            next[i++] = j;
        }
    }
}