Knuth-Morris-Pratt Algorithmus

[Schorschi5566]

Hallo DP,

der Thread ist ja schon etwas älter, aber ich beschäftige mich gerade mit Boyer-Moore & Co.

Habe mal die Fehler im KMP von oben behoben und die Funktion auf die Verwendung mit Strings umgeschrieben. Sollte jetzt auch am Textanfang funktionieren...vielleicht kann's ja der Eine oder Andere gebrauchen.

Delphi-Quellcode:

function TToolBox.PosKMP(const sSearch, sText : String) : Integer;
var
  step : array[1..1024] of Integer;
  i, j , lTarget, lPattern: Integer;
begin
  lTarget := Length(sText);
  lPattern := Length(sSearch);
  result := 0;
  if lTarget * lPattern = 0 then
    Exit;
  i := 1;
  j := 0;
  step[1] := 0;

  repeat
    if (j = 0) or (sSearch[i] = sSearch[j]) then
    begin
      inc(i);
      inc(j);
      if sSearch[j] = sSearch[i] then
        step[i] := step[j]
      else
        step[i] := j;
    end
    else
      j := step[j];
  until i >= lPattern - 1;

  j := 1;
  i := 1;

  while i <= lTarget do
  begin
    if (j = 0) or (sSearch[j] = sText[i]) then
    begin
      inc(i);
      inc(j);
      if j > lPattern then
      begin
        Exit(i - j + 1);
      end;
    end
    else
      j := step[j];
  end;
end;