Algorithmen Kmp- und bm- search

[ellelle]

hallo,

ich muss von meinem lehrer aus ein eigentlich einfache suchprogramm mit kmpsearch und bmsearch schreiben.
ich habe folgende codes von ihm bekommen:

kmpsearch :

Delphi-Quellcode:

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

end;

function  kmpsearch:integer;
var
i,j:integer;
begin
i:=1;j:=1;initnext;
repeat
  if (j=0) or (b[i]=p[i])
    then begin inc(i);inc(j); end
    else begin j:=next[j] end;
until (j>m) or (i>n);
if j>m then kmpsearch:=i-m else  kmpsearch:=i;
end;

für bmsearch :

Delphi-Quellcode:

procedure bminit;                                     
var
j:integer;
ch:char;
begin
setlength(d,m);     
for ch:='a' to 'z' do d[ch]:=m;
for j:=1 to m do d[p[j]]:m-j;

end;

function bmsearch:integer;
var i,j:integer;
begin
i:=m;j:=m;
repeat if a[i]=p[i] then begin
dec(i);dec(j); end
else begin
i:=i+max(d[a[i]]),M-j+1);
j:=m;
end;
until (j<1) or (i>n);
if j<1 then bmsearch:=i+1; else bmsearch:=0;
end;

beide alog. funktionieren nicht! außerdem würde ja immer noch die erste gefundene Stelle in einem String ausgegeben werden. Das kann doch nicht sein. Man könnte diese Problem zwar durch schleifen lösen, aber das würde die suche nicht gerade vereinfachen/schneller machen.

vielleicht kann mir einer von euch helfen.
ich weiß nicht mehr weiter.

danke

mfg elle

[Ultimator]

:shock: Wenn euer Info-Lehrer so eine Code-"Formatierung" benutzt, dann würde ich daraus auch nicht schlau werden :wall:

[ellelle]

hallo,


kann das ja in mein programm schreiben.er wird dann wohl aber nicht so begeistert sein. ;)

kennt denn keiner den passenden algorithmus?

danke
mfg elle

[Steve]

Magst Du uns vielleicht verraten, was A, B, P und NEXT sind? Das wär zuckersüß von Dir :mrgreen:

Gruß
Stephan :dance:

PS: kmpsearch Da gibts soo viel -g-