KMP字符串匹配

给定字符串T和P，求出P在T中出现的次数【KMP模板题】

https://blog.csdn.net/csyifanZhang/article/details/105728330
↑更好的阅读体验

这道题暴力很容易想到，不断的在T中找P的第一个元素，一旦找到了就看看是否T接下来的元素和P匹配，乍一看二分查找+比较好像，但是很容易退化，aaaaaaaaaa匹配aaa，还是很难受的

    string s1, s2;
    while (cin>>s1>>s2)
    {
        ll res = 0, pos = 0, l = s2.size();
        while ((pos = s1.find(s2[0])) >= 0 && s1.size() >= s2.size()) {
            if (s1.substr(pos, l) == s2)res++;
            s1 = s1.substr(pos + 1, s1.size() - 1);
        }
        cout << res << endl;
    }

所以这道题是一道KMP模板题，KMP详细教程，KMP的难点在于预处理next数组，而next数组威力无穷，AC自动机也使用了类似的算法。

ll nextt[MAX];
string s1, s2;

void getNext(string s) {
    memset(nextt, 0, sizeof(nextt));
    ll k = -1, i = 0; nextt[0] = -1;
    while (i < s.size()) {
        if (k == -1 || s[i] == s[k]) {
            if (s[++i] != s[++k])nextt[i] = k;
            else nextt[i] = nextt[k];
        }
        else
            k = nextt[k];
    }
}

ll KMP() {
    ll l1 = s1.size(), l2 = s2.size(), i = 0, j = 0, res = 0;
    while (i < l1) {
        if (j == -1 || s1[i] == s2[j])
            i++, j++;
        else
            j = nextt[j];
        if (j == l2)
            res++, j = nextt[j];//匹配成功
    }
    return res;
}

int main() {
    while (cin >> s1 >> s2) {
        getNext(s2);
        cout << KMP() << endl;
    }
}