KMP算法C代码

发布时间:2017-3-30 4:52:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"KMP算法C代码 ",主要涉及到KMP算法C代码 方面的内容,对于KMP算法C代码 感兴趣的同学可以参考一下。

贴上C代码作参考,关于算法,可以参考网上的博文,但不要参考太多,一两篇相近的即可。

#include <stdio.h>#include <stdlib.h>#include <string.h>/* 获取pattern的next数组 */void get_next(char * pattern, int * next, int len){    int i, index;    for (next[0]=-1, i=1; i<len; i++)    {        if (pattern[i] == pattern[next[i-1]+1])        {            next[i] = next[i-1] + 1;            continue;        }        for (index=next[i-1], next[i]=-1; index!=-1; index = next[index])        {            if (pattern[index+1] == pattern[i])            {                next[i] = index + 1;                break;            }        }    }}int KMP(char * text, int tlen, char * pattern, int plen, int * ptr){    int i=0, tindex=0, pindex=0, count=0,  * next = malloc(sizeof(int) * plen);    get_next(pattern, next, plen);    while (i < tlen)    {        if (pattern[pindex] == text[i])        {            i ++;            pindex ++;            if (pindex == plen)            {                pindex = 0;                ptr[tindex++] = i-plen;            }            continue;        }        if (pindex == 0)        {                i ++;        }        else        {            pindex = next[pindex-1] + 1;        }    }    free(next);    return tindex;}/* 按字符读入文件 */int readText(const char * path, char * buf){    FILE * f;    int size;    f = fopen(path, "r");    if (!f)    {        return -1;    }    fseek(f, 0, SEEK_END);    size = ftell(f);    rewind(f);    size = fread(buf, 1, size, f);    if (size <= 0)    {        size = -1;    }    fclose(f);    return size;}int main(){    char text[2000] = {0}, pattern[30] = "aba";//"abcabdecabcabcd";    int * ptr, count = 0, plen, size = readText("file/text.txt", text), i=0, j;        if (size <= 0)    {        return -1;    }    plen = strlen(pattern);    ptr = malloc((size/plen)*sizeof(int));    count = KMP(text, size, pattern, plen, ptr);    printf("%d results.\n", count);    while (i++ < count)    {        printf("index[%d] : ", i);        for (j=0; j<plen; j++)            printf("%c",text[ptr[i-1]+j]);        printf("\n======================\n");    }    free(ptr);    return 0;}

上一篇:Liferay7 BPM门户开发之42: Liferay核心JSP定制扩展
下一篇:VC++/MFC(VC6)开发技术精品学习资料下载汇总

相关文章

关键词: KMP算法C代码

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款