program searching_samples;     { Suchen in Zeichenfolgen }
uses crt;

const    maxlength_of_Muster = 10;

var a,p  : string;
    m,n  : integer;
    next : array[1..maxlength_of_Muster] of integer;


procedure lies_strings;
begin
 writeln('              *** Suchen in Zeichenfolgen *** ');
 writeln;writeln;
 write('Text-String  =  '); readln(a); N:=length(a);
 write('Muster       =  '); readln(p); M:=length(p);
 writeln;writeln;
end;


function brutesearch(start:integer) :integer;
      (* gibt 0 zurÜck bei Nichtauftreten des Musters im Text A *)
var i,j  :integer;
begin
 i:=start;   j:=1;
 repeat
   if a[i]=p[j] then begin  i:=i+1;   j:=j+1  end
                else begin  i:=i-j+2; j:=1    end;
 until (j>m) or (i>n);
 if j>m then brutesearch:=i-m   else brutesearch:=0
end;


procedure init_next;
var i,j : integer;
begin
 i:=1;  j:=0;  next[1]:=0;
 repeat
   if (j=0) or ( p[i]=p[j] ) then  begin
                                     i:=i+1;
                                     j:=j+1;
                                     next[i]:=j;
                                   end
                             else  j:=next[j];
 until i>=M;
end;


function kmpsearch(start:integer) :integer;
var i,j : integer;
begin
 i:=start;  j:=1;
 if i=1 then init_next;
 repeat
   if (j=0) or ( a[i]=p[j] ) then begin  i:=i+1; j:=j+1  end
                             else j:=next[j];
 until (j>M) or (i>N);
 if j>M then kmpsearch:=i-m
        else kmpsearch:=0;
end;



(*********************************  Main  **********************************)
var s    : integer;
    flag : boolean;

begin
 clrscr;
 lies_strings;
 for s:=1 to maxlength_of_muster do next[s]:=0;

 writeln('**************** Brute-Search ****************');
 writeln;writeln;
 flag:=false;
 s:=0;
 repeat
  s:=brutesearch(s+1);
  if s<>0 then
    begin
     writeln('Das Muster "',p,'" kommt im Text A in der ',s,'. Stelle vor ! ');
     flag:=true;
    end;
  until s=0;
 if not flag then writeln('Das Muster "',p,'" kommt im Text A nicht vor ! ');
 readln;

 writeln('**************** KMP-Search ****************');
 writeln;writeln;
 flag:=false;
 s:=0;
 repeat
  s:=kmpsearch(s+1);
  if s<>0 then
    begin
     writeln('Das Muster "',p,'" kommt im Text A in der ',s,'. Stelle vor ! ');
     flag:=true;
    end;
  until s=0;
 if not flag then writeln('Das Muster "',p,'" kommt im Text A nicht vor ! ');
 readln;

end.