模版——KMP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 const int maxn = 10000;
 6 int f[maxn];
 7 char P[maxn];
 8 char T[maxn];
 9 void getfail(char* P, int *f) {
10     f[0] = f[1] = 0;
11     int n = strlen(P);
12     for(int i = 0; i < n; i++) {
13         int j = f[i];
14         while(j && P[i] != P[j]) j = f[j];
15         f[i+1] = P[i] == P[j] ? j+1 : 0;
16     }
17 }
18 
19 void KMP(char* T, char* P, int* f) {
20     int n = strlen(T), m = strlen(P);
21     getfail(P, f);
22     int j = 0;
23     for(int i = 0; i < n; i++) {
24         while(j && T[i] != P[j]) j = f[j];
25         if(T[i] == P[j]) j++;
26         if(j == m) {
27             printf("%d
", i-m+1);
28             j = 0;
29         }
30     }
31 }