KMP算法

待更新

例题

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

class Solution {
    vector<int> next;
    void getNext(string s){
        int j=-1;
        next[0]=-1;
        int len=s.size();
        for(int i=1;i<len;i++){
            while(j!=-1 && s[i]!=s[j+1]){
                j=next[j];
            }
            if(s[i]==s[j+1]){
                j++;
            }
            next[i]=j;
        }
    }
    int KMP(string text,string pattern){
        int n=text.size(),m=pattern.size();
        next.clear();
        next.resize(m);
        getNext(pattern);
        int j=-1;
        for(int i=0;i<n;i++){
            while(j!=-1 && text[i]!=pattern[j+1]){
                j=next[j];
            }
            if(text[i]==pattern[j+1]){
                j++;
            }
            if(j==m-1){
                return i-m+1;
            }
        }
        return -1;
    }
public:

    int strStr(string haystack, string needle) {
        
        return KMP(haystack,needle);
    }
};