- Delphiartiklar, tips, forum, länksamling - 

      

START | DELPHI | LÄNKARGÄSTBOK 




 Forum

Grundkurs
  »Introduktion
  »Snabbguide
  »Komponenter
  »Händelser
  »Strängar
  »Räkna med Delphi   »Egna typer
  »Selektion
  »Iteration
  »Menyer
  »Funktioner
  »Arraystrukturer

Tips & Tricks
  »Nya tips
  »Blandat
  »Databaser
  »Filer
  »Forms
  »Grafik
  »Internet
  »Komponenter
  »Matematik
  »Multimedia
  »Objekt/ActiveX
  »Skrivare
  »Strängar
  »System
  »Mest lästa tips

Artiklar
  »Delphi och ADO
  »Bygga en DLL
  »Skapa en enkel rapport
  »Hantera registret
  »Enheter, units
  »Klassen TCanvas
  »Använd LookUp Controls

 Nya tips
 Lägg till tips
 Delphilänkar
 Gästbok

 

Karp-Rabin strängsökning Kategori: Strangar
Inlagt: 2004-05-02
Läst: 1401
Inlagt av: Staffan Berg
Beskrivning
Här följer en funktion som söker efter en sträng inuti en annan sträng. Metoden kallas för Karp-Rabin-algoritmen. 
Kod
function search (pat: PATTERN; Text: Text) : integer; 
const 
 b = 131; 
var 
 hpat, 
 htext, 
 Bm, 
 j, 
 m, 
 n   : integer; 
 found : Boolean; 
begin  
 found := False;  
 search := 0;  
 m := length (pat);  
 if m = 0 then  
 begin  
  search := 1;  
  found := true 
 end;  
  
 Bm := 1;  
 hpat := 0;  
 htext := 0;  
 n := length (Text);  
 if n >= m then  
  {*** preprocessing ***}  
  for j := 1 to m do  
  begin  
   Bm := Bm * b;  
   hpat := hpat * b + ord (pat[j]);  
   htext := htext * b + ord (Text[j]) 
  end;  
  
 j := m;  
 //*** search *** 
 while not found do  
 begin  
  if (hpat = htext) and (pat = substr (Text, j - m + 1, m)) then  
  begin  
   search := j - m + 1;  
   found := true 
  end;  
  if j < n then  
  begin  
   j := j + 1;  
   htext := htext * b - ord (Text[j - m]) * Bm + ord (Text[j]) 
  end  
  else  
   found := true 
 end 
end; 

 
 
© Copyright 2005 - Staffan Berg
- Alla rättigheter förbehålles -