unit1.~pas

字符串KMP算法

unit Unit1;

interface

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

const Maxlength=100;
type
String1=record
	str:string[Maxlength];
	length:integer;
end;
type nexttype=array [1..8] of integer;
type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure GetNext(T:string1; var next:nexttype);
//  /*求模式串t的next[j]值存于next[]中*/
var
  j,k:integer;
begin
	j:= 1;
  k:= 0;
	next[1]:= 0;
	while (j < T.length) do
	begin
		if (k = 0) or (T.str[j] = T.str[k]) then
		begin
			j:=j+1;
			k:=k+1;
			next[j] := k;
		end
		else k := next[k];
 end;

 for j:=1 to t.length do form1.Memo1.Lines.Add(inttostr(next[j]));

end;

function KMPIndex(S:String1; start:integer; T:String1; var next:nexttype):integer;
var
  i,j,v:integer;
begin
	i:= start;
  j:= 1;
 	while (i <= S.length) and (j <= T.length) do
	begin
		if (j = 0) or (S.str[i] = T.str[j]) then
		begin
			i:=i+1;
			j:=j+1;
		end
		else j:= next[j];
	end;

	if (j > T.length) then v := i-T.length
	else v := -1;
	KMPIndex:=v;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
	S,T:String1;

	next:nexttype;
  pos:integer;
begin
  s.str:='acabaabaabcacaabc';
  s.length:=17;
  T.str:='abaabcac';
  t.length:=8;
  memo1.Lines.Clear;
	GetNext(T, next);
	pos := KMPIndex(S, 1, T, next);
  memo1.Lines.Add('==========================');
  memo1.Lines.Add('子串位置'+inttostr(pos));
end;

end.