04 字符串与模式匹配

字符串

KMP 算法

int KMP_index(char const *t, char const *p, int const *next) {
    int i = 1;
    int j = 1;
    int n = strlen(t);
    int m = strlen(p);
    while ( (i<=n) && (j<=m) ) {
        if (j==0 || t[i]==p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j==m+1) //匹配成功
        return (i-m);
    else
        return 0;
}

int get_next(char const *p, int *next) {
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (j <= strlen(p)) {
        if ( j==0 || p[i]==p[j] ) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}