Advertisement
majczel23000

Wyszukiwanie wzorca - algorytm Boyera-Moore'a

Jan 11th, 2018
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. #include <time.h>
  5. using namespace std;
  6.  
  7. const int N  = 80;  // długość łańcucha s
  8. const int M  =  3;  // długość wzorca p
  9. const int zp = 65;  // kod pierwszego znaku alfabetu
  10. const int zk = 67;  // kod ostatniego znaku alfabetu
  11.  
  12. string tekst,wzorzec;
  13. int last[zk - zp + 1];
  14.  
  15. void generuj()
  16. {
  17.     srand (time(NULL));
  18.     tekst = "";
  19.     for(int i = 0; i < N; i++)
  20.         tekst += zp + rand() % (zk - zp + 1);
  21.  
  22.     wzorzec = "";
  23.     for(int i = 0; i < M; i++)
  24.         wzorzec += zp + rand() % (zk - zp + 1);
  25.  
  26.     cout << "TEKST: " << tekst<< endl;
  27.     cout << "WZOR : " << wzorzec<< endl;
  28.  
  29.     // dla wzorca obliczamy tablicę last[]
  30.     for(int i = 0; i <= zk - zp; i++)
  31.         last[i] = -1;
  32.     for(int i = 0; i < M; i++)
  33.         last[wzorzec[i] - zp] = i;
  34. }
  35.  
  36. void wykonuj()
  37. {
  38.     // szukamy pozycji wzorca w łańcuchu
  39.     int j;
  40.     int i = 0;
  41.     while(i <= N - M)
  42.     {
  43.         j = M - 1;
  44.         while((j > -1) && (wzorzec[j] == tekst[i + j]))
  45.             j--;
  46.         if(j == -1)
  47.         {
  48.             cout << i << endl;
  49.             i++;
  50.         }
  51.         else
  52.             i += max(1,j - last[tekst[i + j] - zp]);
  53.     }
  54. }
  55.  
  56. int main(){
  57.  
  58.     generuj();
  59.     wykonuj();
  60.  
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement