You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
75 lines
1.7 KiB
C
75 lines
1.7 KiB
C
/* License: AGPLv3 or later. https://www.gnu.org/licenses/licenses.html
|
|
*
|
|
* Exercise 6 - Karp-Rabin String Search (Week 7)
|
|
* Name: Manish
|
|
* Student Login: *****
|
|
*
|
|
* Compile as:
|
|
* $ gcc -std=c11 -Wall -o ex6 ex6.c
|
|
*
|
|
* NOTE: There is error that using some small no. like 500 give incorrect (incomplete) results. Still not figured out why.
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
char t[5001];
|
|
char s[11];
|
|
int t_len = 0;
|
|
int s_len = 0;
|
|
unsigned long prime = 5;
|
|
unsigned long mod = 18446744073709551557UL; // prime < 2^64
|
|
unsigned long precomputed_prime_exponent = 1;
|
|
|
|
int main(void)
|
|
{
|
|
printf("Enter file name: ");
|
|
char filename[257];
|
|
// Assuming filename/file path won't be longer than 256 characters
|
|
scanf("%256s", filename);
|
|
|
|
FILE* file = fopen(filename, "r");
|
|
if (!file)
|
|
{
|
|
perror(filename);
|
|
exit(EXIT_FAILURE);
|
|
}
|
|
|
|
fscanf(file, "%5000s %10s", t, s);
|
|
t_len = strlen(t);
|
|
s_len = strlen(s);
|
|
|
|
unsigned long t_hash = t[0]%5;
|
|
unsigned long s_hash = s[0]%5;
|
|
|
|
for (int i=1; i < s_len; i++)
|
|
{
|
|
precomputed_prime_exponent = (precomputed_prime_exponent*prime)%mod;
|
|
t_hash = (((prime*t_hash)%mod) + (t[i]%5))%mod;
|
|
s_hash = (((prime*s_hash)%mod)+ (s[i]%5))%mod;
|
|
}
|
|
|
|
for (int i=0; i < t_len-s_len; i++)
|
|
{
|
|
if (t_hash == s_hash)
|
|
{
|
|
if (strncmp(&t[i], s, s_len) == 0)
|
|
printf("%d ", i);
|
|
}
|
|
// %5 for characters and %mod every + & * part of equation
|
|
t_hash = (
|
|
(((prime*
|
|
(t_hash -
|
|
((precomputed_prime_exponent*(t[i]%5))%mod)
|
|
))%mod) +
|
|
(t[i+s_len]%5))
|
|
%mod);
|
|
}
|
|
printf("\n");
|
|
|
|
fclose(file);
|
|
|
|
return 0;
|
|
}
|