KMP算法实现-C语言

KMP 算法：

#include
#include
#include

void prefix_table(char pattern[],int prefix[],int n){
    prefix[0] = 0; //前缀表的第一位规定为0
    int len = 0;
    int i = 1; //从第1位开始比较
    while(i < n){
        if(pattern[i] == pattern[len]){
            len++;
            prefix[i] = len;
            i++;
        }
        else{
            if(len > 0){
            len = prefix[len-1];
            }
            else{
                prefix[i] = 0;
                i++;
            }
        }
    }
}

void move_prefix_table(int prefix[],int n){
    for(int i = n-1; i > 0 ; i--){
        prefix[i] = prefix[i-1];
        
    }
    prefix[0] = -1;
}

//kmp
void kmp_search(char text[],char pattern[]){
    int m = strlen(text);
    int n = strlen(pattern);
    int i=0,j=0;
    //i指向text[]，j指向pattern[]
    
    int *prefix  = (int *)malloc(sizeof(int)*n);
    prefix_table(pattern,prefix,n);
    move_prefix_table(prefix,n);
    while(i