Knuth-Morris-Pratt Algorithmus

[Klaus01]

Guten Abend,

der verlinkte Code ist anscheinend nicht ganz o.k.
Er findet nur Teilwörter mit der Länge 2 und auch nur dann
wenn sie nicht am Anfang des zu durchsuchenden Strings stehen.

Das mit der Teilwortlänge von 2 habe ich unten berichtigt.
Weiter besteht das Problem, dass kein Teilwort gefunden wird
wenn es im zu durchsuchenden String am Anfang steht.
Grüße
Klaus

Delphi-Quellcode:

function kmp(const target,pattern: pchar;const LTarget, lPattern: Integer):Integer;
var
  step : array[0..255] of Integer;
  i,j : Integer;

begin
  result := -1;
  i:=0;
  j := -1;
  if lTarget * lPattern = 0 then
    exit;
  step[0] := -1;

  repeat
    begin
      if ( j = -1) or (pattern[i] = pattern[j]) then
        begin
          inc(i);
          inc(j);


          if pattern[j] = pattern[i] then
            step[i] :=step[j]
          else
            step[i] := j;
        end
      else
        j:=step[j];
    end;
  until i >= lPattern -1;  // hier ein > eingefügt
  j:=  -1;
  i:=0;
  while i < lTarget do
    begin
      if (j = -1) or (pattern[j] = target[i]) then
        begin
          inc(i);
          inc(j);
          if j >= lPattern then
            begin
              result := i-j+1;
              exit;
            end;
        end
      else
        j:= step[j];
    end;
end;