1. #include<stdio.h>
2. #include<stdlib.h>
3.  
4. int dlugosc(char *lan);
5. int* init_next(char *wzor);
6. int KMP(char *tekst, char *wzor, int *next);
7. int BM(char *tekst, char *wzor);
8. int main()
9. { char *tekst="ABCDEFGH";
10.         char *wzor = "FGH";
11.         int *next;
12.         int cos;
13.         next = init_next(wzor);
14.         printf("%in", KMP(tekst,wzor,next));
15.         printf("%in", BM(tekst,wzor));
16.         system("PAUSE");
17.  
18. }
19. int dlugosc(char *lan)
20. {
21.         int i;
22.         for(i=0; lan[i] != '�';i++){}
23.         return i;
24. }
25. int* init_next(char *wzor)
26. {
27.         int i,j;
28.         int M = dlugosc(wzor);
29.         int *next = malloc(M*sizeof(int));
30.         next[0] = -1;
31.         for(i=0,j=-1;i<M-1;i++,j++,next[i]=j)
32.         {
33.                 while((j>=0) && (wzor[i] != wzor[j]))
34.                 {j=next[j];}
35.         }
36. return next;
37. }
38. void init_shift(char *wzor, int *shift)
39. {int i;
40. int K=256;
41. int M=dlugosc(wzor);
42. for(i=0;i<K;i++)
43.         {
44.                 shift[i]=M;
45.         }
46. for(i=0;i<M;i++)
47.         {
48.                 shift[wzor[i]]=M-i-1;
49.        
50.         }
51. }
52. int KMP(char *tekst, char *wzor, int *next)
53. {
54.         int i,j;
55.         int N=dlugosc(tekst);
56.         int M=dlugosc(wzor);
57.         for(i=0,j=0;i<N && j<M;i++,j++)
58.         {while((j>=0)&& (tekst[i] != wzor[j]))
59.                 {
60.                         j=next[j];
61.                 }
62.  
63.         }
64.         if(j==M)
65.         {
66.                 return i-M;
67.         }
68.         else return -1;
69.  
70. }
71. int BM(char *tekst, char *wzor)
72. { int i,j,x,shift[256];
73.   int M = dlugosc(wzor);
74.   int N = dlugosc(tekst);
75.   init_shift(wzor,shift);
76.   for(i = M-1, j=M-1;j>=0;i--,j--)
77.         while(tekst[i] !=wzor[j])
78.           { x= shift[tekst[i]];
79.                 if(M-j > x) i+=M-j;
80.                 else i+=x;
81.                 if(i>=N) return -1;
82.                 j=M-1;
83.           }
84.   return i+1;
85.  }
86.