首页 > 编程语言 > 详细

KMP算法详解

时间:2020-03-16 01:42:41      阅读:78      评论:0      收藏:0      [点我收藏+]

KMP算法主要工作是计算next数组(这里我们认为数组从0开始)

模式字符串为m,伪代码如下:

void Next(m,next){

int i=0,j=-1;

next[0]=-1;

while(i<strlen(m))

{

  if(j==-1||m[i]==m[j])

  {

    i++;

    j++;

    next[i]=j;

  }

  else j=next[j];

}

}

实例代码如下:

 1 //KMP算法实现,计数从零开始
 2 #include<stdio.h>
 3 #include<string.h>
 4 char c[100];
 5 char model[20];
 6 char *p,*q;
 7 int main()
 8 {
 9     int n;
10     int KMP(char*,char*);
11     p=c;
12     q=model;
13     printf("请输入主串:\n");
14     gets(p);
15     printf("请输入模式串:\n");
16     gets(q);
17     n=KMP(p,q);
18     printf("%d\n",n);
19     return 0;
20 }
21 
22 void Next(char* a,int* b)
23 {
24     int len=strlen(a);  //字符串长度是有效字符的长度
25     int i=0,j=-1;
26     b[0]=-1;
27     while(i<len)
28     {
29         if(j==-1||a[j]==a[i])
30         {
31             ++i;
32             ++j;
33             b[i]=j;
34         }
35         else
36         {
37             j=b[j];
38         }
39     }
40 }
41 
42 int KMP(char *a,char*b)  //a为主串,b为模式串
43 {
44     int len1=strlen(a);
45     int len2=strlen(b);
46     int next[20];
47     int i=0,j=0;
48     Next(b,next);
49     while(i<len1&&j<len2)
50     {
51         if(j==-1||a[i]==b[j])
52         {
53             i++;
54             j++;
55         }
56         else j=next[j];
57     }
58     if(j==len2) return i-j;
59     else return -1;
60 }

 

运行结果:

技术分享图片

 

KMP算法详解

原文:https://www.cnblogs.com/bboykaku/p/12501232.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!