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

力扣链接(简单)：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string

给你两个字符串 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 仅由小写英文字符组成

个人题解

暴力算法时间复杂度：$ O(nm) $

KMP 算法时间复杂度：求 Next 数组 \(O(m)\) + 匹配过程 \(O(n)\)

class Solution {
public:
    void getNext(int *next, string& s) {
        // 初始化next, j 表示前缀末尾，i 表示后缀末尾
        int j = 0; 
        next[0] = j;

        // 这里 i 从 1 开始，因为后缀指的是满足不包含第一个元素的所有子串
        for(int i = 1; i < s.size(); i++) {
            // 处理前后缀匹配失败的情况：回退，这里要注意 j > 0
            while(j > 0 && s[i] != s[j]){
                // 找匹配失败的前一位（匹配成功的部分）对应的回退位置
                j = next[j - 1];    
            }
            // 处理匹配成功的情况，继续向后匹配
            if(s[i] == s[j]) j++;
            // j 其实就代表匹配成功的前缀长度
            // next 存的就是从 0 到当前下标的这个子串的最大相等前后缀的长度，不断更新
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        // 这里用 KMP 算法
        int next[needle.size()];
        // 构造 next 数组
        getNext(next, needle);

        // 开始匹配，可以类比构造 next 数组的过程
        // i 指向文本串，j 指向模式串
        int i = 0, j = 0;   
        for(; i < haystack.size(); i++) {
            // 匹配失败，回退
            while(j > 0 && haystack[i] != needle[j]) j = next[j - 1];
            // 匹配成功
            if(haystack[i] == needle[j]) j++;

            // 如果 j 到模式串末尾了，代表子串匹配成功
            if(j == needle.size()){
                return i - j + 1;
            }
        }

        return -1;
    }
};