KMP算法详解

 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 }