algorytm.org

Implementacja w Delphi/Pascal

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm KMP (Knutha-Morrisa-Pratta) - Implementacja w Delphi/Pascal
Ocena użytkownikóww: *****  / 1
SłabyŚwietny
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.
Dodaj komentarz