Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <conio.h>
- #include <string.h>
- #include <stdlib.h>
- int dlugosc(char*lan);
- int* init_next(char*wzor);
- int KMP (char* tekst,char* wzor, int* next);
- int main()
- {
- char wzor[256];
- char tekst[256];
- int* next;
- int M,N,i,j,ind;
- int P[256];//maksymalna dlugosc wzorca to 100 symboli
- printf("Podaj tekst\n");
- fflush(stdin);
- scanf("%255[^\n]s", tekst);
- printf("Podaj wzorzec\n");
- fflush(stdin);
- scanf("%255[^\n]s", wzor);
- N=dlugosc(tekst);
- M=dlugosc(wzor);
- next=init_next(wzor);
- ind=KMP(tekst,wzor,next);
- printf("Indeks poczatku wzorca w tekscie=%d\n",ind);
- }
- int dlugosc(char*lan)
- {
- int i=0;
- while(lan[i]!='\0')i++;
- return i;
- }
- int* init_next(char*wzor)
- {
- int i,j,M=dlugosc(wzor),*next=malloc(M*sizeof (int));
- next[0]=-1;
- for(i=0,j=-1;i<M-1;i++,j++,next[i]=j)
- while((j>=0)&&(wzor[i]!=wzor[j]))
- j=next[j];
- return next;
- }
- int KMP (char* tekst,char* wzor, int* next)
- {
- int i,j,N=dlugosc(tekst),M=dlugosc(wzor);
- for(i=0,j=0;i<N && j<M; i++, j++)
- while((j>=0) && (tekst[i]!=wzor[j]))
- j=next[j];
- if(j==M)
- return i-M;
- else
- return -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement