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

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

示例1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= $10^4$
haystack 和 needle 仅由小写英文字符组成

题目来源：力扣（LeetCode）链接

题解：

方法一：暴力匹配

class Solution {
    public int strStr(String haystack, String needle) {
        int l1 = haystack.length();
        int l2 = needle.length();
        // 如果要找的字符串比被找的字符串长，就直接返回-1
        if (l1 < l2) {
            return -1;
        }
        char[] arr = needle.toCharArray();
        // 遍历被查找的字符串
        for (int i = 0; i < l1; i++) {
            int index = 0;
            // 如果第一个字符匹配就继续查找，一旦有不匹配的就退出内层循环
            for (int j = i; j < i + l2; j++) {
                if (haystack.charAt(j) == arr[index]) {
                    index++;
                } else {
                    break;
                }
            }
            // 内层循环结束，如果 index=l2 说明找到了，此时 i 就是第一个匹配的下标
            if (index == l2) {
                return i;
            }
        }
        // 如果循环结束，且没有返回，则说明没有找到
        return -1;
    }
}

方法二：KMP 算法 (参考代码随想录里面的讲解点我跳转)

class Solution {
    public int strStr(String haystack, String needle) {
        // 如果 needle 字符串为 null 或 ""，则直接返回 0
        if (needle.length() == 0) {
            return 0;
        }
        // 调用方法得到 needle 的前缀表
        int[] next = new int[needle.length()];
        getNext(next, needle);
        // 指针 j 表示 needle 的下标
        int j = 0;
        // 遍历字符串 haystack
        for (int i = 0; i < haystack.length(); i++) {
            // 如果字符不匹配，指针 j 就根据前缀表 next 回退
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            // 如果字符匹配，那么 i 和 j 同时向后移动
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            // 如果 j 等于字符串 needle 的长度，则说明第一次完全匹配，返回对应的下标
            if (j == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        // 如果字符串遍历完成后，依然没有返回，则说明没找到
        return -1;
    }
    // 获取 needle 的前缀表
    public void getNext (int[] next, String s) {
        // j 的初始值对应长度为前 1 个字符的子串的最长相同前后缀
        int j = 0; 
        // 长度为前 1 个字符的子串，最长相同前后缀为 0
        next[0] = j;
        // 遍历字符串 needle 直接从下标 1 开始
        for (int i = 1; i < s.length(); i++) {
            // 如果前后缀不相同，那么 j 就要回退，一直到相等时结束
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            // 如果前后缀相等，就用 j 记录
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            // 把长度为前 i 个字符的子串，最长相同前后缀记录到 next 数组对应的位置
            next[i] = j;
        }
    }
}