代码随想录 28. 找出字符串中第一个匹配项的下标（KMP算法）

题目：

代码（首刷自解 暴力 2024年1月18日）：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int nstr = 0;
        for (int i = 0; i < n; ++i) {
            if (haystack[i] == needle[0]) {
                int hstr = i;
                while (haystack[hstr] == needle[nstr] && nstr < needle.size()) {
                    if (nstr == needle.size() - 1) {
                        return i;
                    }
                    ++hstr;
                    ++nstr;
                } 
                nstr = 0;
            }
        }
        return -1;
    }
};

代码（首刷看解析?KMP算法?2024年1月18日）：

class Solution {
public:
    void getNext(string& str, vector<int>& next) {
        /*  作用：构建str字符串的前缀表 */
        int j = 0;
        for (int i = 1; i < str.size(); ++i) {
            while (j > 0 && str[i] != str[j]) {
                j = next[j - 1];
            }
            if (str[i] == str[j]) {
                ++j;
            }
            next[i] = j;
        }
        for (int i = str.size() - 2; i >= 0; --i) {
            next[i + 1] = next[i];
        }
        next[0] = -1;
    }   

    int strStr(string haystack, string needle) {
        int n = needle.size();
        if(n == 0) return 0;
        vector<int> next(n);
        getNext(needle,next);

        int j = 0;
        for (int i = 0; i < haystack.size(); ++i) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j];
            }
            if (haystack[i] == needle[j]) {
                ++j;
            }
            if (j == n) return i - j + 1;
        }
        return -1;
    }
};

? ? ? ? 构建前缀表的具体实现我选择了构建完后整体 右移 1 位，因为我认为这样比较好理解，当整体右移一位时,当主串和模式串不匹配，next[index]就会是上一个匹配点的位置。

? ? ? ? PS：搞懂了KMP+写出无BUG代码花了整整3小时