#define MODULUS 127
#include <stdio.h>
#include <strings.h>
/* Corrected the code found in href=http://www.sparknotes.com/cs/searching/hashtables/section4.rhtml */
int rksearch(char* pattern, char* text)
{
int pattern_hash, text_hash, pattern_len, num_iterations, i;
/* are the pattern and the text legitimate strings? */
if (pattern == NULL || text == NULL) return -1;
/* get the lengths of the strings and the number of iterations */
pattern_len = strlen(pattern);
num_iterations = strlen(text) - pattern_len + 1 ;
/* Do initial hashes */
pattern_hash = hash(pattern);
text_hash = hashn(text, pattern_len);
/* Main comparison loop */
for (i = 0; i < num_iterations; i++) {
if (pattern_hash == text_hash &&
!strncmp(pattern, &(text[i]), pattern_len)) return i;
text_hash = hash_increment(text, i, text_hash, pattern_len);
}
/* Pattern not found so return -1 */
return -1;
}
/* hash function for fingerprinting */
int hash(char* str)
{
int sum = 0;
int k;
int i=0;
k = strlen(str);
while (i<k) {
sum = (sum+ (int) (str)); i++;
}
return sum % MODULUS;
}
int hashn(char* str, int n)
{
int sum;
char *str1;
int i;
str1 = (char *) malloc(n);
for (i=0;i<n;i++)
str1=str;
str1[n]='\0';
sum = hash(str1);
return sum;
}
int hash_increment(char* str, int prevIndex, int prevHash, int keyLength)
{
int val = (prevHash - ((int) str[prevIndex])
+ ((int) str[prevIndex + keyLength])) % MODULUS;
return (val < 0) ? (val + MODULUS) : val;
}
int main()
{
char *text;
char *pattern;
text = (char *) malloc(300);
pattern = (char *) malloc(45);
scanf("%s %s", text, pattern);
printf("Text String %s\n", text);
printf("Pattern String %s\n", pattern);
printf("Pattern is found in position %d\n", rksearch(pattern,text));
exit(0);
}
[/i]
