实现了代码很烂的KMP算法

先是看算法导论和数据结构

后来又自己又上YouTube看视频

就是这个视频,讲得很清晰

然后附上代码做纪念:

int KMP(char * string, char * pattern){
    int len=(int)strlen(pattern),
        l=(int)strlen(string),
        *next;
    next=(int*)malloc((len+1)*sizeof(int));
    for(int i=1,j=0;i<len;i++){
        if(pattern[i]==pattern[j]) {
            next[i]=j+1;
            j++;
            continue;
        }
        if(j==0) continue;
        i--;
        j=(next[j]==0)?0:(next[j]-1);
    }
    for(int i=0,j=0;i<l;i++){
        if(string[i]==pattern[j]){
            j++;
            if(j==len) return i+1-len;
            continue;
        }
        if(j==0) continue;
        i--;
        j=next[j-1];
    }
    return -1;
}

以后再改进吧!继续努力💪!


已发布

分类

来自

标签: