28. 找出字符串中第一个匹配项的下标

实现 strStr() 函数。

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

说明：

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

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

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：

输入：haystack = "", needle = ""
输出：0

提示：

• 0 <= haystack.length, needle.length <= 5 * 104
• haystack 和 needle 仅由小写英文字符组成

思路

字符串前缀和后缀的定义：

• 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
• 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

KMP算法。先计算next数组。自算出每个字符前面子串的相等前缀子串和后缀子串的最大长度。

然后开始和目标字符串进行匹配，遇到不行的字符时，使用该位置的最长前缀子串位置开始重新匹配。

注意：str1 = “”, str2 = “” 的情况，此时要返回0

public static int strStr(String haystack, String needle) {
    int[] next = buildNext(needle);
    int i = 0, j = 0;
    while (i < haystack.length() && j < needle.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            // 当前字符相等，两个指针后移
            i++;
            j++;
        } else if (j == 0) {
            // 当前字符与首字符也不相等，i 后移一位，j 从0开始匹配
            i++;
        } else {
            // 从 j 位置的前缀子串的前缀子串位置开始匹配
            j = next[j - 1];
        }
    }
    return j == needle.length() ? i - j : -1;
}

public static int[] buildNext(String s) {
    int[] next = new int[s.length()];
    next[0] = 0;
    int p = 0;
    for (int i = 1; i < next.length; i++) {
        // 前后缀不相同，向前回退
        while (p > 0 && s.charAt(i) != s.charAt(p)) {
            p = next[p - 1];
        }
        // 前后缀相同
        if (s.charAt(i) == s.charAt(p)) {
            // 这里容易写错为 next[i] = next[p] + 1，
            // 注意上面 p = next[p - 1]，所以此时 p 就是当前当前匹配位置的前缀长度
            next[i] = p + 1;
        }
        p = next[i];
    }
    return next;
}