串的KMP匹配

KMP算法下面只写个代码, 网上有很多讲解(还没见一个讲得很清楚的, 用文字也确实难讲清楚), 想学习的直接看严大妈的视频讲解严蔚敏KMP讲解, 多看几遍总能懂.

typedef char String[225];

// get_next数组
void get_next(String T, int *next) {
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i] != T[j]) next[i] = j;
            else T[i] = next[j];
            
        } else {
            j = next[j];
        }
    }
    
}

int get_KMP(String S, String T, int pos) {
    int i = pos;
    int j = 1;
    int next[255];
    get_next(T, next);
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || T[j] == S[i]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (i > S[0]) {
        return 0;
    } else {
        return i - T[0];
    }
}