//www.algorytm.org
//Algorytm KR (Karpa-Rabina) - wyszukiwanie wzorca
//(c)2006 Tomasz Lubinski

program Algorytm_KR;

uses
  Forms,
  Math,
  Sysutils;

{$R *.RES}
{$Apptype console}

var
m,n,i,j:Integer;
rm,h1,h2:Int64;
wzorzec:String;
tekst:String;

const q:Integer=117899; //możliwie duża liczba pierwsza
      r:Integer=256;    //liczba symboli alfabetu

//oblicza a^b mod m
function power_modulo_fast(a: Integer; b: Integer; m: Integer): Integer;
var
   i: Integer;
   x: Int64;
begin
   result := 1;
   x := a mod m;

   i := 1;
   while (i<=b) do
      begin
         x := x mod m;
         if ((b and i) <> 0) then
            begin
               result := (result * x) mod m;
            end;
         x := x * x;
         i := i shl 1;
      end;
   result := result mod m;
end;

//Algorytm KR (Karpa-Rabina) - wyszukiwanie wzorca
begin
writeln('Podaj tekst');
readln(tekst);
writeln('Podaj wzorzec');
readln(wzorzec);

n:=length(tekst);
m:=length(wzorzec);

rm:=power_modulo_fast(r, m-1, q);
h1:=0;
h2:=0;
writeln('Indeksy poczatkow wzorca w tekscie');
//algorytm Hornera do obliczenia funkcji haszującej h(wzorzec)
for i:=1 to m do
   begin
      h1:=((h1*r) + Ord(wzorzec[i]));
      h1:=h1 mod q;
   end;
//algorytm Hornera do obliczenia funkcji haszującej h(tekst[1..m])
for i:=1 to m do
   begin
      h2:=((h2*r) + Ord(tekst[i]));
      h2:=h2 mod q;
   end;

i:=1;
while i<n-m+1 do
        begin
        j:=0;
        if h1=h2 then while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
        if j=m then writeln((IntToStr(i)));
        h2:=h2-Ord(tekst[i])*rm;
        h2:=h2*r;
        h2:=h2+Ord(tekst[i+m]);
        h2:=h2 mod q;
        if (h2<0) then h2:=h2+q;
        i:=i+1;
        end;
j:=0;
if h1=h2 then while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
if j=m then writeln((IntToStr(i)));

readln;
end.