KMP补档

inline void get_fail(char *st) {
    fail[0] = -1;
    for (int i = 1, j = -1; st[i]; ++i) {
        while (j >= 0 && st[j + 1] != st[i]) {
            j = fail[j];
        }
        if (st[j + 1] == st[i]) {
            ++j;
        }
        fail[i] = j;
    }
}


inline int KMP(char *T, char *P) {
    get_fail(P);
    int ret = 0;
    int length = strlen(P) - 1;
    for (int i = 0, j = -1; T[i]; ++i) {
        while (j >= 0 && P[j + 1] != T[i]) {
            j = fail[j];
        }
        if (T[i] == P[j + 1]) {
            ++j;
        }
        if (j == length) {
            ++ret;
            j = fail[j];
        }
    }
    return ret;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注