Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <math.h>
- #include <string>
- #include <sys/time.h>
- int p = 2, N = 2013889;
- int hit_count = 0;
- struct timeval start, end;
- void timer_start()
- {
- gettimeofday(&start, 0);
- }
- void timer_end(char *what)
- {
- gettimeofday(&end, 0);
- printf("%s: %ldusec\n", what, (end.tv_sec*1000000 + end.tv_usec) - (start.tv_sec*1000000 + start.tv_usec));
- }
- int power(int base, int exp)
- {
- if(exp == 0) return 1;
- else return (int)pow(base, exp);
- }
- int hash(char *string)
- {
- int result = 0, i = 0;
- while(string[i] != '\0')
- {
- result += (string[i]*(power(p,(strlen(string)-i-1)))) % N;
- i++;
- }
- return result % N;
- }
- int main()
- {
- FILE *text = fopen("biblia.txt", "r");
- std::string stext;
- while(!feof(text))
- {
- char c = fgetc(text);
- stext += c;
- }
- timer_start();
- char *string = "Jerusalem";
- int string_hash = hash(string);
- char *rect = (char*)malloc(strlen(string)*sizeof(char));
- int i;
- for(i = 0; i < strlen(string); i++)rect[i] = stext[i];
- int rect_hash = hash(rect);
- if(string_hash == rect_hash)
- {
- if(strcmp(string, rect) == 0) hit_count++;
- }
- int stextlen = stext.length();
- int b = (power(p,(strlen(rect)-1) ));
- int len = strlen(string);
- for(int i = len; i < stextlen; i++)
- {
- char c = stext[i];
- rect_hash -= (rect[0]*b);
- rect_hash = (rect_hash * p);
- rect_hash += c;
- rect_hash %= N;
- int k;
- for(k = 0; k < len-1; k++)rect[k] = rect[k+1];
- rect[len-1] = c;
- if(string_hash == rect_hash)
- {
- if(memcmp(string, rect, len) == 0) hit_count++;
- }
- }
- timer_end("rabin karp");
- printf("%d\n", hit_count);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement