《算法导论》KMP的一种实现

仅做练习记录使用。

模式串next值计算代码根据《算法导论》描述实现。

匹配过程自行实现。

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
int * ComputeOverlay(const char* input){
    if(input == NULL|| strlen(input)== 0)
        return NULL;
    int len = strlen(input);
    int *overlay = (char*) malloc(sizeof(int)*len);
    overlay[0] = 0;
    int i = 1;
    for(;i<len;i++){
        overlay[i] = 0;
        if(input[i] == input[overlay[i-1]]){
            overlay[i] = overlay[i-1]+1;
        }
        else if(input[i] == input[0]){
            overlay[i]++;
        }
    }
    return overlay;

}
int KMP(const char* src, const char* pattern){
    if(!src && !pattern) return -1;
    int srclen = strlen(src);
    int patternlen = strlen(pattern);
    int *overlay = ComputeOverlay(pattern);
    int srcIndex = 0;
    int patternIndex = 0;
    while(srcIndex<srclen && patternIndex < patternlen){
        printf("compare src[%d] and pattern[%d] \n", srcIndex,patternIndex);
        if(src[srcIndex] == pattern[patternIndex]){
            srcIndex++;
            patternIndex++;
        }
        else if(patternIndex == 0){
            srcIndex ++;
        }
        else{
            patternIndex = overlay[patternIndex-1];
            printf("pattern back to %d \n",patternIndex);
        }

    }
    if(patternIndex == patternlen){
        return srcIndex - patternIndex;
    }
    return -1;
}

int main(){
    char * pattern = "abababca";
    int* overlay = ComputeOverlay(pattern);
    int i = 0;
    for(;i<strlen(pattern);i++){
        printf("%c ",pattern[i]);
    }
    printf("\n");

    for(i=0;i<strlen(pattern);i++){
        printf("%d ",overlay[i]);
    }

    printf("\n");
    printf("Found at %d \n", KMP("ababbabababcad", pattern));
}