Skip to content

Instantly share code, notes, and snippets.

@shkesar
Created October 3, 2016 14:46
Show Gist options
  • Save shkesar/bcc332cff39f572e3c94115870c18306 to your computer and use it in GitHub Desktop.
Save shkesar/bcc332cff39f572e3c94115870c18306 to your computer and use it in GitHub Desktop.
Rabin-Karp string matching algorithm
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define INVALID_OP -1
#define NOT_FOUND -2
typedef enum {TRUE = 0, FALSE} boolean;
int rabin_karp(char *P, size_t m, char *T, size_t n, int d) {
int p = 0, t = 0;
int h = (int)pow(d, m-1) % d;
for (int i = 0; i < n-m+1; i++) {
p = (d * p + P[i]-'0') % d;
t = (d * t + T[i]-'0') % d;
}
for (int s = 0; s < n-m+1; s++) {
printf("%d\n", t);
if (p == t) {
if (strncmp(P, T+s, m) == 0)
printf("Patterns occurs wth shift %d\n", s);
}
if (s < n - m)
t = (d * (t - (T[s+1] - '0')*h) + T[s+m+1] - '0') % d;
}
return 0;
}
int main(int argc, char **argv) {
rabin_karp(argv[1], strlen(argv[1]), argv[2], strlen(argv[2]), 10);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment