[kmp]leetcode28：实现 strStr() (easy)

题目：

题解：

思路：严蔚敏版 kmp 算法实现

class Solution {
public:
    int strStr(const string& s, const string& p) {
        int n=s.size(),m=p.size();
        int i=0,j=0;
        auto next=get_next(p);
        while(i
            if(j==-1||s[i]==p[j])++i,++j;
            else j=next[j];
            if(j==m)return i-m;
        }
        return -1;
    }

    // 严版kmp算法实现：next[j]=k-1 相同前缀和后缀的最长长度为 k-1，不匹配时指针 j 回退到 next[j] 的位置，也就是位置 k
    // next[j]是不包括p[j]的相同前缀和后缀的长度，因此每次匹配失败后，都会回退到相同前缀的下一个位置与s[i]继续进行匹配。
    vector get_next(const string& p){
        int m=p.size();
        // 由于next[j]是不算p[j-1]这个后缀的，所以要计算p[m-1]这个后缀，需要使用next[m]，这里数组大小要多一个。
        // next[0]=-1 是因为字符串 p 中的字符是从下标 0 开始的，其他无相同前缀和后缀长度的next值为0，表示重新从下标0开始进行匹配
        vector next(m+1,-1);
        // 指针 j 指向后缀，指针 k 指向前缀
        int j=0,k=-1;
        while(j
            // 匹配成功的话，next[j+1]=k+1，表示之前的p[0...k]与p[j-k...j]已经匹配成功，此时的将j移动到下一个位置j+1，指针k也移动下一个位置k+1，那么next[j+1]=k+1，为相同前缀和后缀的长度为k的下一个位置k+1
            // 当j=m-1时，会计算next[m]的值的
            if(k==-1||p[k]==p[j])next[++j]=++k;
            // 匹配失败，k指针回到相同前缀和长度的下一个位置
            // 若没有可以匹配的前缀和后缀，那么k最终会回到-1的位置
            else k=next[k];
        }
        return next;
    }
};