Advertisement
evandrix

Rabin-Karp Exact String Match

Feb 25th, 2012
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5. #include <string>
  6. #include <sys/time.h>
  7.  
  8. int p = 2, N = 2013889;
  9. int hit_count = 0;
  10.  
  11. struct timeval start, end;
  12. void timer_start()
  13. {
  14. gettimeofday(&start, 0);
  15. }
  16. void timer_end(char *what)
  17. {
  18.     gettimeofday(&end, 0);
  19.     printf("%s: %ldusec\n", what, (end.tv_sec*1000000 + end.tv_usec) - (start.tv_sec*1000000 + start.tv_usec));
  20. }
  21.  
  22.  
  23. int power(int base, int exp)
  24. {
  25.     if(exp == 0) return 1;
  26.    
  27.     else return (int)pow(base, exp);
  28. }
  29.  
  30. int hash(char *string)
  31. {
  32.     int result = 0, i = 0;
  33.     while(string[i] != '\0')
  34.     {
  35.         result += (string[i]*(power(p,(strlen(string)-i-1)))) % N;
  36.         i++;
  37.     }
  38.    
  39.     return result % N;
  40. }
  41.  
  42. int main()
  43. {
  44.     FILE *text = fopen("biblia.txt", "r");
  45.     std::string stext;
  46.     while(!feof(text))
  47.     {
  48.         char c = fgetc(text);
  49.         stext += c;
  50.     }
  51.    
  52.     timer_start();
  53.    
  54.    
  55.     char *string = "Jerusalem";
  56.     int string_hash = hash(string);
  57.     char *rect = (char*)malloc(strlen(string)*sizeof(char));
  58.     int i;
  59.     for(i = 0; i < strlen(string); i++)rect[i] = stext[i];
  60.     int rect_hash = hash(rect);
  61.    
  62.     if(string_hash == rect_hash)
  63.     {
  64.         if(strcmp(string, rect) == 0) hit_count++;
  65.     }
  66.  
  67.     int stextlen = stext.length();
  68.     int b = (power(p,(strlen(rect)-1) ));
  69.     int len = strlen(string);
  70.     for(int i = len; i < stextlen; i++)
  71.     {
  72.         char c = stext[i]; 
  73.        
  74.         rect_hash -= (rect[0]*b);
  75.         rect_hash =  (rect_hash * p);
  76.         rect_hash += c;
  77.         rect_hash %= N;
  78.        
  79.         int k;             
  80.         for(k = 0; k < len-1; k++)rect[k] = rect[k+1];
  81.                
  82.         rect[len-1] = c;
  83.        
  84.        
  85.         if(string_hash == rect_hash)
  86.         {
  87.             if(memcmp(string, rect, len) == 0) hit_count++;
  88.         }
  89.     }
  90.     timer_end("rabin karp");
  91.     printf("%d\n", hit_count);
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement