Ocena użytkownikóww: ***** / 1
Nadesłany przez Tomasz Lubiński, 26 lipca 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
Algorytm KMP - Delphi/Algorytm_KMP.dpr:
//www.Algorytm.org
//Algorytm KMP (Knutha-Morrisa-Pratta) - wyszukiwanie wzorca
//(c)2001 Tomasz Lubinski
program Algorytm_KMP;
uses
Forms,
SysUtils,
math;
{$R *.RES}
{$Apptype console}
var
m,n,i,j,t:Integer;
wzorzec:String;
tekst:String;
P: array of Integer;
begin
writeln('Podaj tekst');
readln(tekst);
writeln('Podaj wzorzec');
readln(wzorzec);
n:=length(tekst);
m:=length(wzorzec);
SetLength(P,m+1);
//algorytm obliczania tablicy P
P[0]:=0; P[1]:=0; t:=0;
for j:=2 to m do
begin
while (t>0) and (wzorzec[t+1]<>wzorzec[j]) do t:=P[t];
if wzorzec[t+1]=wzorzec[j] then t:=t+1;
P[j]:=t;
end;
//Algorytm KMP (Knutha-Morrisa-Pratta)
writeln('Indeksy poczatkow wzorca w tekscie');
i:=1; j:=0;
while i<=n-m+1 do
begin
j:=P[j];
while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
if j=m then writeln((IntToStr(i)));
i:=i+max(1,j-P[j]);
end;
readln;
end.
