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 <= 104
• haystack 和 needle 仅由小写英文字符组成

双重for循环，先大后小

class Solution {
    public int strStr(String haystack, String needle) {
        // 获取原字符串和匹配字符串的长度
        int n = haystack.length(), m = needle.length();
        
        // 遍历原字符串的每一个可能的起始位置。先遍历大的，再遍历小的。
        // 例如，[0...m-1] 是第一个子串，[1...m] 是第二个子串，[2...m+1] 是第三个子串，以此类推。
        for (int i = 0; i <= (n - 1) - m + 1; i++) {
            // 初始化一个标志位，表示当前子串是否匹配
            boolean flag = true;
            
            // 遍历匹配字符串的每一个字符，即遍历以i为起点的长度为m的字符串。重点。
            for (int j = 0; j < m; j++) {
                // 如果在任意位置字符不匹配，设置标志位为 false 并退出内层循环，遍历以下一个元素为起点的长度为m的字符串
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            
            // 如果标志位为 true，表示当前子串匹配，返回起始位置 i
            if (flag) {
                return i;
            }
        }
        
        // 如果遍历完成后没有找到匹配子串，返回 -1
        return -1;
    }
}

• 时间复杂度： $O(n \times m)$ ，其中 $n$ 是字符串 haystack 的长度， $m$ 是字符串 needle 的长度。最坏情况下我们需要将字符串 needle 与字符串 haystack 的所有长度为 $m$ 的子串均匹配一次。
• 空间复杂度： $O(1)$ 。我们只需要常数的空间保存若干变量。

KMP

本质是空间换时间。