自动机算法基础

自己慢慢写代码：
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 
 5 /*
 6 BF匹配算法，最原始的模式匹配算法 
 7 */ 
 8 int BFmatch(char* s,char* p)
 9 {
10     int i,j;
11     j=0;
12     i=0;
13     while(i < strlen(s)){
14         j=0;
15         while( (s[i] == p[j]) && (j < strlen(p))){
16              i++;
17              j++;       
18         }        
19         if(j == strlen(p))
20            return i-j;
21         i = i-j+1; 
22     }   
23     return -1;
24 }
25 
26 /**
27 KMP匹配算法，原始版的KMP算法 
28 **/
29 
30 void init_next(char *p, int* next)
31 {
32       int i,j;
33       if(next == NULL) return;
34       next[0] = -1; 
35        
36       i=0; 
37       j = -1; 
38       while(i < strlen(p)-1){
39              if( j == -1 || p[i] == p[j]){
40                  i++;
41                  j++;
42                  if(p[i]!= p[j])  next[i] = j;
43                  else next[i] =next[j];
44              }else{
45                 j = next[j];      
46              } 
47       } 
48       
49 }
50  
51 int KMPmatch(char *s, char* p)
52 {
53      int i,j;
54      int* next; 
55      i=0;
56      j = -1;
57      next = (int *)malloc(strlen(p)*sizeof(int));
58      
59      init_next(p,next);
60       
61      while(i < strlen(s)){
62           if(j == -1 || s[i] == p[j]){  //如果相等，后移 
63                i++;
64                j++;        
65           }else{
66                 j =  next[j]; 
67           } 
68           if(j == strlen(p)){
69              free(next);
70              return i-j;     
71           } 
72      }
73       
74      free(next);
75       
76      return -1; 
77 }
78 
79 
80 
81 int main()
82 {
83      char s[10];
84      char p[10];
85      int i; 
86      printf("input string:");scanf("%s",s);
87      printf("input mode string:");scanf("%s",p);
88      i = KMPmatch(s,p);
89      printf("output match id:%d\n",i+1);
90      system("pause");
91      return 0; 
92 }