Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cstdlib>
- #include <time.h>
- using namespace std;
- const int N = 80; // długość łańcucha s
- const int M = 3; // długość wzorca p
- const int zp = 65; // kod pierwszego znaku alfabetu
- const int zk = 67; // kod ostatniego znaku alfabetu
- string tekst,wzorzec;
- int last[zk - zp + 1];
- void generuj()
- {
- srand (time(NULL));
- tekst = "";
- for(int i = 0; i < N; i++)
- tekst += zp + rand() % (zk - zp + 1);
- wzorzec = "";
- for(int i = 0; i < M; i++)
- wzorzec += zp + rand() % (zk - zp + 1);
- cout << "TEKST: " << tekst<< endl;
- cout << "WZOR : " << wzorzec<< endl;
- // dla wzorca obliczamy tablicę last[]
- for(int i = 0; i <= zk - zp; i++)
- last[i] = -1;
- for(int i = 0; i < M; i++)
- last[wzorzec[i] - zp] = i;
- }
- void wykonuj()
- {
- // szukamy pozycji wzorca w łańcuchu
- int j;
- int i = 0;
- while(i <= N - M)
- {
- j = M - 1;
- while((j > -1) && (wzorzec[j] == tekst[i + j]))
- j--;
- if(j == -1)
- {
- cout << i << endl;
- i++;
- }
- else
- i += max(1,j - last[tekst[i + j] - zp]);
- }
- }
- int main(){
- generuj();
- wykonuj();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement