开发者社区> 问答> 正文

谁有KMP算法的C语言实现啊

谁有KMP算法的C语言实现啊

展开
收起
知与谁同 2018-07-22 15:05:42 2847 0
2 条回答
写回答
取消 提交回答
  • 其基本思想是:每当匹配过程中出现字符串比较不等时,不需回溯i指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。

    #include <stdio.h>
    #include <string.h>
    int index_KMP(char *s,char *t,int pos);
    void get_next(char *t,int *);

    char s[10]="abcacbcba";
    char t[4]="bca";
    int next[4];
    int pos=0;

    int main()
    {
    int n;
    get_next(t,next);
    n=index_KMP(s,t,pos);
    printf("%d",n);
    return 0;
    }

    int index_KMP(char *s,char *t,int pos)
    {
    int i=pos,j=1;
    while (i<=(int)strlen(s)&&j<=(int)strlen(t))
    {
    if (j==0||s[i]==t[j-1])
    {
    i++;
    j++;
    }
    else j=next[j];
    }
    if (j>(int)strlen(t))
    return i-strlen(t)+1;
    else
    return 0;
    }

    void get_next(char *t,int *next)
    {

    int i=1,j=0;
    next[0]=next[1]=0;
    while (i<(int)strlen(t))
    {
    if (j==0||t[i]==t[j])
    {
    i++;
    j++;
    next[i]=j;
    }
    else j=next[j];
    }

    }
    2019-07-17 22:55:56
    赞同 展开评论 打赏
  • #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #include<assert.h>
    #include<stdlib.h>
    void getNext(const char * t,int * Next)//get the Next array
    {
    int k=-1;
    int j=0;
    int size=strlen(t);
    Next[0]=-1;
    while(j<size)
    {
    if(k==-1||t[j]==t[k])//if k==-1 there are two conditions
    //one is this is the first time entering the loop
    { //if t[j]==t[k] get the next[j+1] directly
    k++;//the other is the end of the iteration cos k==-1;
    j++;
    Next[j]=k;//whatever Next[j]=k
    }
    else
    k=Next[k];
    }
    }
    int myStrstr(const char * Dest,const char *subStr)//find the starting position of the sub
    { //in the Dest through KMP
    int destSize=strlen(Dest);
    int subSize=strlen(subStr);
    int i,j;
    int * Next=(int *)(malloc(sizeof(int)*subSize));
    i=j=0;
    assert((Dest!=NULL)&&(subStr!=NULL));
    getNext(subStr,Next);
    while(i<destSize&&j<subSize)
    {
    if(j==-1||Dest[i]==subStr[j])//if j==-1 the main string need match the next elements
    { //and the subString begin from the beginning
    i++; //if Dest[i]==subStr[j] both string need shift to the
    j++; // next elements
    }
    else
    j=Next[j]; //if match fail,glide back to Next[j]
    }
    if(j==subSize)return i-j;
    return -1;
    }
    int main()
    {
    char *temp,*sub,* Dest;//to store the substring to be matched
    int ch;
    unsigned int templen,length=20*sizeof(char);
    unsigned int mlength=20*sizeof(char);//the original length of the memory
    sub=(char*)malloc(length);
    Dest=(char*)malloc(length);
    if(sub==NULL||Dest==NULL)//allocation failure
    {
    printf("memory allocate failure\n");
    exit(0);
    }
    temp=sub;
    printf("please input the substring:\n");
    while((ch=getchar())!=10)//read the sub String
    {
    if((temp-sub)/sizeof(char)==length)//if running out of the memory
    {
    templen=length;
    sub=realloc(sub,length+=20*sizeof(char));
    if(sub==NULL)
    {
    printf("sub memory allocate failure\n");
    exit(0);
    }
    temp=sub+templen*sizeof(char);//reset the temp cos the sub may change its value
    }
    *temp++=ch;
    }
    *temp='\0';
    temp=Dest;
    printf("please input the mainstring:\n");
    while((ch=getchar())!=10)//read the main String
    {
    if((temp-Dest)/sizeof(char)==mlength)
    {
    templen=mlength;
    Dest=realloc(Dest,mlength+=20*sizeof(char));//if running out of the memory
    if(Dest==NULL)
    {
    printf("sub memory allocate failure\n");
    exit(0);
    }
    temp=Dest+templen*sizeof(char);//reset the temp cos the Dest may change its value
    }
    *temp++=ch;
    }
    *temp='\0';
    printf("the starting position is :%d\n",myStrstr(Dest,sub));//get the starting position
    free(Dest);
    free(sub);
    return 0;
    }
    2019-07-17 22:55:56
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载