Knuth-Morris-Pratt Algorithmus

[alzaimar]

Hier noch ein paar gute Links:
1. Schrittweise Demonstration
2. Definition, Erklärung, Implementierung, Live-Demo

[Görly]

eine programdarstellung wie sie im 1. link erfolgt wäre natürlich wahnsinn zur verdeutlichung des kmp algorithmus. aber duch die umschreibung meines programms ist das nich zu schaffen, oder?

mfg görly

[Gausi]

Eine Suchanimation ist auch mit Delphi machbar, allerdings ist das nicht mal eben gemacht. Für einen Vortrag hab ich mal ein kleines Programm geschrieben, was einige der gängigen Suchalgorithmen animiert und "gegeneinander antreten lässt". Knuth-Morris-Pratt ist da auch dabei.

Ich hab für hier mal ein kleines Label eingebaut, damit du nicht schummeln kannst

[alzaimar]

[omata]

@Gausi: Ein echt geiles Programm

[Görly]

ou du bist n held ! geniale sache. aber die lehrerin würd mir eh niemals abkaufen das ich das allein geschrieben hätte hast ja gesehen wo meine probleme anfangen !

ein riesen dankeschön.

mal nebenbei, wie lange hast du gebraucht das prog. zu schreiben? und wie lange brauch man um solche erfahrung in sachen delphi zu erlangen. bin jetz auch voll im delphi-fieber

greetz görly

[Gausi]

Wie lange ich dafür gebraucht habe, weiß ich nicht mehr. War aber nicht übermäßig lang - das ist auch mehr so nebenbei entstanden. Irgendwo hier schwirrt auch ein Thread mit ner frühen Version des Programms rum, was man da noch durch Mausbewegungen zum Absturz bringen konnte - Threadprogrammierung mit Bitmaps ist etwas doof.

(Und vielleicht kann es ja auch der nächste Vortragende gebrauchen - wo Knuth-Morris-Pratt vorkommt, ist Boyer-Moore meistens nicht weit weg. )

[Görly]

na wirst es nich glauben ich muss beides erklähren daher bin ich so wahnsinnig begeistert!

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