1 void getfail(char *p,int* f)
 2 {
 3     int m = strlen(p);
 4     f[0] = 0;
 5     f[1] = 0;
 6     for (int i = 1;i < m;i++)
 7     {
 8         int j = f[i];
 9         
10         while (j && p[i] != p[j]) j = f[j];
11         
12         f[i+1] = p[i] == p[j] ? j+1 : 0;
13     }
14 }
15 
16 void find(char *t,char *p,int* f)
17 {
18     int n = strlen(t),m = strlen(p);
19     
20     getfail(p,f);
21     
22     int j = 0;
23     
24     for (int i = 0;i < n;i++)
25     {
26         while (j && p[j] != t[i]) j = f[j];
27         if (p[j] == t[i]) j++;
28         if (j == m) printf("%d\n",i-m+1);
29     }
30 }