实现strStr

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

class Solution {
public:
    //構造next前綴表
    void getNext(int* next, const string& s){
        //从左往右为前缀，从右往左为后缀。
        int j = -1;//前缀指针,指到前缀的末尾,同时也是前缀最长相等前后缀长度-1（下标即为长度）
        next[0] = j; //初始化，数组第一个元素回退到j的位置
        //i为后缀，i指向的都是后缀的末尾
        for(int i = 1; i < s.size(); i++){//因为第0位的元素前后缀都为空子串，所以从第二位i=1开始比较
            while(j >= 0 && s[i] != s[j + 1]){
                j = next[j]; 
                // 前缀后缀不等的时候回退到j指针的前一位的位置。因为j实际上记录的是j-1，即前一位的下标。所以直接赋值next[j].回退过程是递推过程，因为每个子串都在向前递增，如果上一个子串存在有已经匹配的相等前后缀，就从上一个子串的位置更新(j的更新原理，如果上个循环有匹配的前后缀，下个循环继续使用j，如果继续能匹配，就继续更新j。如果无法匹配了，就执行回退)。
                // 这个时候的j如果要查询回退位置，就回退到上一个能匹配的位置，如果还是不能匹配就继续回退，最终回退到初始化位置 -1.很难理解的应该递推规程，因为j不需要直接初始化，而且可以从上一个能匹配的位置接着匹配
            }
            if(s[j + 1] == s[i]){//此时前后缀相等，记录的长度+1
                 j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        int j = -1;
        getNext(next, needle); //构造前缀表
        for(int i = 0; i < haystack.size(); i++){
            while(j >= 0 && haystack[i] != needle[j + 1]){
                j = next[j];//回退操作
            }
            if(haystack[i] == needle[j + 1]){
                j++;
            }
            //下标等于模式串长度，说明全部和模式串相匹配
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

对我来说真的很难，理解kmp思想太费事了。把代码拷了一份到本地，逐行跟才理解。主要是回退操作用到的递推思想，光看很难理解。

具体理解都写在注释里了