public int strStr(String haystack, String needle) {
        int len = haystack.length(), subLen = needle.length();
        if (subLen == 0) return 0;
        if (len == 0) return -1;


        int[] next = getNext(needle);
        int i = 0, j = 0;  i指向haystack, j指向needle
        while (i < len) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++; j++;
                if (j == subLen) return i - j;
            } else {
                 回溯
                j = next[j];
            }
        }

        return -1;
    }

    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        next[0] = -1;

        int pre = 0, post = 1;  pre前缀指针, post后缀指针
        while (post < s.length()) {
            if (pre == -1 || s.charAt(pre) == s.charAt(post)) {
                pre++;
                post++;
                if (post < s.length()) next[post] = pre;  匹配-> 表示可以经过next[post]回溯到pre
            } else {
                 不匹配, 回溯到上个pre位置尝试匹配当前post
                pre = next[pre];
            }
        }
        return next;
    }