KMP模式匹配

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

int *compute_prefix(const char *pattern) {
    int *prefix;
    int i, k, size;

    assert(pattern);
    size = strlen(pattern);
    prefix = malloc(size * sizeof(int));
    memset(prefix, '\0', size * sizeof(int));
    for (i = 1; i < size; i++) {
        k = prefix[i-1];
        while (1) {
            if (pattern[i] == pattern[k]) {
                prefix[i] = k+1;
                break;
            }
            if (k == 0) break;
            k = prefix[k-1];
        }
    }
    return prefix;
}

static int *prefix = NULL;
static char *pattern = NULL;
static int *get_prefix(const char *text) {
    if (!prefix || strcmp(text, pattern)!=0) {
        pattern = text;
        prefix = compute_prefix(text);
    }
    return prefix;
}

const char *kmp_matcher(const char *text, const char* pattern) {
    int i, *prefix;
    const char *tptr, *pptr, *ptr=NULL;

    assert(text);
    assert(pattern);
    tptr = text;
    pptr = pattern;
    prefix = get_prefix(pattern);
    while (1) {
        for(i=0; *tptr++==*pptr++ && *tptr!='\0' && *pptr!='\0'; i++);
        if (*pptr == '\0') {
            ptr = tptr-i-1;
            break;
        }
        else if (*tptr == '\0')
            break;
        pptr = (i==0) ? pattern : pattern+prefix[i-1];
    }
    return ptr;
}

int main(int argc, char *argv[]) {
    char *input;
    int i, *lens;
    if (argc == 1) {
        printf("empty input\n");
        return 0;
    }
    input = argv[1];
    lens = compute_prefix(input);
    printf("%s\n", input);
    for(i = 0; i < strlen(input); i++) {
        printf("%d", lens[i]);
    }
    char *pattern = "aacd";
    char *pos = kmp_matcher("aabbaacdielsoaacd", pattern);
    putchar('\n');
    printf("%s\n", pos);
    pos = kmp_matcher(pos+4, pattern);
    putchar('\n');
    printf("%s\n", pos);
    return 0;
}

 test.zip