KMP 模板。详见 https://www.cnblogs.com/Patt/p/10498191.html

【模板】KMP.cpp

int get_next(const char *P, const int *fail, const char ch, int i) {
    while (i != -1 && P[i] != ch)
        i = fail[i];
    return i + 1;
}

void get_fail(const char *P, int *fail, const int len_P) {
    fail[0] = -1;
    for (int i = 1; i <= len_P; i++) {
        fail[i] = get_next(P, fail, P[i - 1], fail[i - 1]);
    }
}

int KMP_match(const char *P, const int len_P, const char * T, const int len_T, const int *fail) {
    int cnt = 0;
    for (int i = 0, j = 0; i < len_T; ++i) {
        j = get_next(P, fail, T[i], j);
        if (j == len_P) {
            j = fail[j];
            ++cnt;
        }
    }
    return cnt; // P 在 T 中出现的次数
}