JZTXT

模板 KMP

发布时间 2023-07-29 02:18:44作者: wuyoudexian
namespace KMP {
    void getNext(string t, vector<int> &nxt) {
        nxt.resize(t.size() + 1);
        for(int i = 1, j = 0; i < t.size(); i++) {
            while(j && t[i] != t[j]) {
                j = nxt[j];
            }
            j += (t[i] == t[j]);
            nxt[i + 1] = j;
        }
    }

    int find(string s, string t) {
        vector<int> nxt;
        getNext(t, nxt);
        for(int i = 0, j = 0; i < s.size(); i++) {
            while(j && s[i] != t[j]) {
                j = nxt[j];
            }
            j += (s[i] == t[j]);
            if(j == t.size()) {
                return i - t.size() + 2;
            }
        }
        return -1;
    }

    bool find(string s, string t, vector<int> &ans) {
        ans.clear();
        vector<int> nxt;
        getNext(t, nxt);
        for(int i = 0, j = 0; i < s.size(); i++) {
            while(j && s[i] != t[j]) {
                j = nxt[j];
            }
            j += (s[i] == t[j]);
            if(j == t.size()) {
                ans.emplace_back(i - t.size() + 2);
                j = nxt[j];
            }
        }
        return !ans.empty();
    }
}