一.KMP算法

28. 找出字符串中第一个匹配项的下标以这道题为例，最简单的方法是双重遍历，这里学一下KMP算法更高效

什么是前缀表，对于一个待匹配的串“aabaaf”，其前缀表为0 1 0 1 2 0表示从开头到每个位置为止的前缀后缀相同部分的长度

class Solution {
public:
    void getNext(vector<int> &next, const string& s) {
        int j = 0;
        next[0] = 0;
        int n = s.size();
        for(int i=1;i<n;i++){
            while(j>0&&s[j]!=s[i]){
                j=next[j-1];
            }
            if(s[j]==s[i]){
                j++;
            }
            next[i] = j;
        }
    };
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }

        vector<int> answers;
        vector<int> next(needle.size());
        getNext(next, needle);
        int j = 0;
        for(int i=0;i<haystack.size();i++){
            
            while(j>0&&haystack[i]!=needle[j]){
                j = next[j-1];
            }

            if(haystack[i]==needle[j]){
                j++;
                if(j==needle.size()){
                    answers.emplace_back(i-needle.size()+1);
                }
            }
        }
        for(auto &x:answers){
            cout<<x<<" ";
        }

        if(answers.size()>0){
            return answers[0];
        }

        return -1;
    }
};