пластическая акробатика

АНДРЕЙ «ORC» СЕРЕГИН

Спецвыпуск: Хакер, номер #071, стр. 071-034-3

Procedure KMPPrefix;

var S, P : array;

A, B, C : integer;

Begin

P[1]:=0;

B:=0;

for A:=2 to C do

begin

while (B>0) and (S[B+1]<>S[A]) do

B:=P[B];

if S[B+1]=S[A] then

B:=B+1;

P[A]:=B;

end;

End;

А поиск с использованием нашей функции будет выглядеть так:

var n : integer;

T : array;

Begin

KMPPrefix;

k:=0;

for i:=1 to n do

begin

while (k>0) and (S[k+1]<>T[i]) do

k:=P[k];

if S[k+1]=T[i] then

k:=k+1;

if k=m then

begin

k:=P[k];

Exit;

end;

end;

End.

Метод Уильяма-Флойда

procedure TreeMethod (var Arr : Array; N : Integer);

var

A : Integer;

B : Integer;

C : Integer;

D : Integer;

Tmp : Double;

begin

if N=1 then Exit;

A := 2;

repeat

D := A;

while D<>1 do

begin

C := D div 2;

if Arr[C-1]>=Arr[D-1] then

begin

D := 1;

end

else

begin

Tmp := Arr[C-1];

Arr[C-1] := Arr[D-1];

Arr[D-1] := Tmp;

D := C;

end;

end;

A := A+1;

until not (A<=N);

A := N-1;

repeat

Tmp := Arr[A];

Arr[A] := Arr[0];

Arr[0] := Tmp;

D := 1;

while D<>0 do

begin

C := 2*D;

if C>A then

begin

D := 0;

end

else

begin

if C<A then

begin

if Arr[C]>Arr[C-1] then

begin

C := C+1;

end;

end;

if Arr[D-1]>=Arr[C-1] then

begin

D := 0;

end

else

begin

Tmp := Arr[C-1];

Arr[C-1] := Arr[D-1];

Arr[D-1] := Tmp;

D := C;

end;

end;

end;

Dec (A);

until not (A>=1);

end;

Метод фон Неймана

procedure MergeMethod (var Arr : Array; N : Integer);

var

Q : Boolean;

A : Integer;

A1 : Integer;

A2 : Integer;

N1 : Integer;

N2 : Integer;

ergeLen : Integer;

Tmp : Double;

TmpArr : Array;

begin

SetLength(TmpArr, N-1+1);

MergeLen := 1;

Q := True;

while MergeLen<n do

begin

if Q then

begin

A := 0;

while A+MergeLen<=n do

begin

A1 := A+1;

A2 := A+MergeLen+1;

n1 := A+MergeLen;

n2 := A+2*MergeLen;

if n2>n then

begin

n2 := n;

end;

while (A1<=n1) or (A2<=n2) do

begin

if A1>n1 then

begin

while A2<=n2 do

begin

A := A+1;

TmpArr[A-1] := Arr[A2-1];

A2 := A2+1;

end;

end

else

begin

if A2>n2 then

begin

while A1<=n1 do

begin

A := A+1;

TmpArr[A-1] := Arr[A1-1];

A1 := A1+1;

end;

end

else

begin

if Arr[A1-1]>Arr[A2-1] then

begin

A := A+1;

TmpArr[A-1] := Arr[A2-1];

A2 := A2+1;

end

else

begin

A := A+1;

TmpArr[A-1] := Arr[A1-1];

A1 := A1+1;

end;

end;

end;

end;

end;

A := A+1;

while A<=n do

begin

TmpArr[A-1] := Arr[A-1];

A := A+1;

end;

end

else

begin

A := 0;

while A+MergeLen<=n do

begin

A1 := A+1;

A2 := A+MergeLen+1;

n1 := A+MergeLen;

n2 := A+2*MergeLen;

if n2>n then

begin

n2 := n;

end;

while (A1<=n1) or (A2<=n2) do

begin

if A1>n1 then

begin

while A2<=n2 do

begin

A := A+1;

Arr[A-1] := TmpArr[A2-1];

A2 := A2+1;

end;

end

else

begin

if A2>n2 then

begin

while A1<=n1 do

begin

A := A+1;

Arr[A-1] := TmpArr[A1-1];

A1 := A1+1;

end;

end

else

begin

if TmpArr[A1-1]>TmpArr[A2-1] then

begin

A := A+1;

Arr[A-1] := TmpArr[A2-1];