字符串匹配KMP算法

详细算法描述见《算法导论32.4》，以下是C实现：

[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <string.h>  
4.   
5. //预处理：所需时间为O(m)，空间O(m)  
6. void compute_prefix_func(char sp[], int p[])  
7. {  
8.     int m, k, q;  
9.     m = strlen(sp);  
10.     p[0] = 0;  
11.     k = 0;  
12.     for (q = 1; q < m; q++) {  
13.         while ((k > 0) && (sp[k] != sp[q])) {  
14.             k = p[k-1];  
15.         }  
16.         if (sp[k] == sp[q])  
17.             k++;  
18.         p[q] = k;  
19.     }  
20.       
21.     for (q = 0; q < m; q++)  
22.         printf("p[%d] = %d\n", q, p[q]);  
23. }  
24.   
25. //匹配：所需时间为O(n)  
26. void kmp_matcher(char st[], char sp[])  
27. {  
28.     int n, m, q, i;  
29.     int *p;  
30.     n = strlen(st);  
31.     m = strlen(sp);  
32.     p = (int *)malloc(sizeof(int) * m);  
33.     compute_prefix_func(sp, p);  
34.     q = 0; //Number of characters matched  
35.     for (i = 0; i < n; i++) {  
36.         while ((q > 0) && (sp[q] != st[i])) {  
37.             q = p[q-1]; //Next character does not match  
38.         }  
39.         if (sp[q] == st[i]) //Next character matches  
40.             q++;  
41.         if (q == m) { //Is all of P matched?  
42.             printf("Pattern occurs with shift %d\n", i - (m - 1));  
43.             q = p[q-1]; //Look for the next match  
44.         }  
45.     }  
46.     free(p);  
47. }  
48.   
49. int main(void)  
50. {  
51.     char st[] = "abcdabcabcabcabcdabcabcdabcabcabcd";  
52.     char sp[] = "abcabcd";  
53.     kmp_matcher(st, sp);  
54.     return 1;  
55. }  

KMP算法图文解析

KMP算法详解