KMP算法（思路未补）

 1 #include <stdio.h>
 2 #include <string.h> 
 3 #include <stdlib.h>
 4 
 5 typedef int Position;
 6 #define NotFound -1
 7 
 8 void BuildMatch(char* pattern, int* match)
 9 {
10     Position i, j;
11     int m = strlen(pattern);
12     match[0] = -1;
13 
14     for (j = 1; j < m; j++) {
15         i = match[j - 1];
16         while ((i >= 0) && (pattern[i + 1] != pattern[j]))
17             i = match[i];
18         if (pattern[i + 1] == pattern[j])
19             match[j] = i + 1;
20         else match[j] = -1;
21     }
22 }
23 
24 Position KMP(char* string, char* pattern)
25 {
26     int n = strlen(string);
27     int m = strlen(pattern);
28     Position s, p, * match;
29 
30     if (n < m) return NotFound;
31     match = (Position*)malloc(sizeof(Position) * m);
32     BuildMatch(pattern, match);
33     s = p = 0;
34     while (s < n && p < m) {
35         if (string[s] == pattern[p]) {
36             s++; p++;
37         }
38         else if (p > 0) p = match[p - 1] + 1;
39         else s++;
40     }
41     return (p == m) ? (s - m) : NotFound;
42 }
43 
44 int main()
45 {
46     char string[] = "This is a simple example.";
47     char pattern[] = "simple";
48     Position p = KMP(string, pattern);
49     if (p == NotFound) printf("Not Found.
");
50     else printf("%s
", string + p);
51     return 0;
52 }