home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / diskmags / amiga_9301b.lha / Suchalgorithmen / Listing 6 < prev   
Encoding:
Text File  |  1992-12-15  |  614 b   |  30 lines
  1. /* Das Robin-Karp-Verfahren ermöglicht lineare Suchzeiten,
  2.  * unabhängig von der Eingabe
  3.  */
  4.  
  5. #define q 33554393
  6. #define d 32
  7.  
  8. long RK_Search(unsigned char *Puffer,
  9.                unsigned char *Pattern,
  10.                long size)
  11. {
  12.   long i,j,M=strlen(Pattern),N=size,dM=1,h1=0,h2=0;
  13.  
  14.   for( i=1; i<M ; i++ )
  15.     dM=(d*dM)%q;
  16.  
  17.   for( i=0; i<M ;i++ ) {
  18.     h1 = (h1 << 5 + (long)Pattern[i]) % q;
  19.     h2 = (h2 << 5 + (long)Puffer[i]) % q;
  20.   }
  21.  
  22.   for( i=0; h1 != h2 ;i++ ) {
  23.     h2 = (h2 + d*q - (long)Puffer[i] * dM) % q;
  24.     h2 = (h2<<5 + (long)Puffer[i+M]) % q;
  25.     if( i > N-M )
  26.       return N;
  27.   }
  28.   return i;
  29. }
  30.