Knuth-Morris-Pratt Algorithmus

[Görly]

so wie gesagt das program ist ja fertig. soweit is das klasse. nur mir ist aufgefallen das wenn ich ein wort mehrmals im satz habe und dieses suche er mir nur die stelle des anfangsbuchstaben von 1. wort ausgibt. dazu kommt das ich bei diesem program automatisch die zeit messen lassen muss das hab ich wie folglich im quellcode zu sehen ist auch schon hinbekommen. doch da der satz nicht ausreichend lang ist gibt mir dieser zähler keinen wert aus, wenn ich nich vorher einen haltepunkt im quellcode festlege. meine lehrerin war der meinung das sei nicht anders lösbar und da dachte ich frag ich euch nochmal !
schauts euch einfach mal an:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Label3: TLabel;
    Edit3: TEdit;
    procedure Button1Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
function knuth_morris_pratt(const target, pattern : PChar; const lTarget, lPattern : integer) : integer;
var
        step : array[0..255] of integer;
        i,
        j    : integer;
        begin
        result := -1;
        if ltarget * lpattern = 0 then exit;
        i := 0;
        j := -1;
        step[0] := -1;

        repeat
        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];
        until i = lpattern -1;
        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;


procedure TForm1.Button1Click(Sender: TObject);
var i, t:integer; s1,s2:string;
begin
  t := gettickcount;

s1:=edit1.Text;
s2:=edit2.Text;
i:=knuth_morris_pratt(pchar(s1),pchar(s2),length(s1),length(s2));
label2.Caption:=inttostr(i);

Edit3.Text := floattostrf((gettickcount-t)*0.001,fffixed,10,2);
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  edit1.Text:= '';
  edit2.Text:= '';
  label2.Caption:= '';
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
close;
end;

procedure TForm1.Button4Click(Sender: TObject);
begin
edit1.text:= 'hallo liebe info freune! info mit frau müller macht sp.-spa.-sp (ach scheiß drauf, macht auf jeden fall iwas)';
edit2.Text:= 'frau müller';
end;

end.

[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;