/*
Program realizujący algorytm Karpa–Rabina zmodyfikuj tak, aby znajdował wszystkie
wystąpienia wzorca w tekście.
*/

#include
#include
#include

using namespace std;

const int N = 997;
const int M = 26;

int Potega(int podst, int wykl)
{
int w = 1;
while (wykl > 0)
{
if(wykl%2 == 1)
w = (w*podst)%N;
wykl = wykl/2;
if (wykl > 0)
podst = (podst*podst)%N;
}
return w;
}

int Hash0(string s)
{
int w = 0;
for(int i = 0; i < s.size(); i++)
w = ((w*M)%N + s[i] - 'a')%N;
return w;
}

int Hash1(int h0, int jd, char ch)
{
int w = (h0-jd)%N;
if(w < 0)
w = w + N;
return ((w*M)%N + ch - 'a')%N;
}

vector Znajdz(string w, string t)
{
int i, p = 0, dw = w.size(), dt = t.size();
int hw = Hash0(w);
int ht = Hash0(t.substr(0, dw));
int pot = Potega(M, dw-1);
vector wynik;

while(p <= dt - dw)
{
if (hw == ht)
{
i = 0;
while(i wynik;

cout << "Podaj tekst: ";
cin >> t;
cout << "Podaj wzorzec: ";
cin >> w;

wynik = Znajdz(w, t);

if (wynik.size() == 0)
cout << "Wzorzec nie wystepuje w tekscie";
else
{
cout << "Pozycje wzorca: ";

for (int i = 0; i < wynik.size(); i++)
cout << wynik[i] << " ";
}

return 0;
}