SHARE
TWEET

Untitled

a guest Mar 21st, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <string.h>
  4. #include <stdlib.h>
  5. int dlugosc(char*lan);
  6. int* init_next(char*wzor);
  7. int KMP (char* tekst,char* wzor, int* next);
  8.  
  9. int main()
  10. {
  11.    
  12.     char wzor[256];
  13.     char tekst[256];
  14.     int* next;
  15.     int M,N,i,j,ind;
  16.     int P[256];//maksymalna dlugosc wzorca to 100 symboli
  17.     printf("Podaj tekst\n");
  18.     fflush(stdin);
  19.     scanf("%255[^\n]s", tekst);
  20.     printf("Podaj wzorzec\n");
  21.     fflush(stdin);
  22.     scanf("%255[^\n]s", wzor);
  23.     N=dlugosc(tekst);
  24.     M=dlugosc(wzor);
  25.     next=init_next(wzor);
  26.     ind=KMP(tekst,wzor,next);
  27.     printf("Indeks poczatku wzorca w tekscie=%d\n",ind);
  28.  
  29.    
  30. }
  31.  
  32.  
  33. int dlugosc(char*lan)
  34. {
  35.     int i=0;
  36.     while(lan[i]!='\0')i++;
  37.     return i;
  38. }
  39.  
  40.  
  41. int* init_next(char*wzor)
  42. {
  43.     int i,j,M=dlugosc(wzor),*next=malloc(M*sizeof (int));
  44.     next[0]=-1;
  45.     for(i=0,j=-1;i<M-1;i++,j++,next[i]=j)
  46.         while((j>=0)&&(wzor[i]!=wzor[j]))
  47.             j=next[j];
  48.             return next;
  49. }
  50.  
  51. int KMP (char* tekst,char* wzor, int* next)
  52. {
  53.     int i,j,N=dlugosc(tekst),M=dlugosc(wzor);
  54.     for(i=0,j=0;i<N && j<M; i++, j++)
  55.         while((j>=0) && (tekst[i]!=wzor[j]))
  56.             j=next[j];
  57.     if(j==M)
  58.         return i-M;
  59.     else
  60.         return -1;
  61. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top