Inital commit

1 files changed, 70 insertions, 0 deletions

diff --git a/kmp.c b/kmp.c
new file mode 100644
index 0000000..d5923bf
--- /dev/null
+++ b/kmp.c
@@ -0,0 +1,70 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include "kmp.h"
+
+/* KMP implementation stolen from Github user cagdass*/
+
+int* init_array(int size) {
+  int* arr = (int*)malloc(size * sizeof(int));
+  int i;
+  for(i = 0; i < size; i++) {
+    arr[i] = 0;
+  }
+
+  return arr;
+}
+
+int kmp(char* t,size_t tlen, char* p,size_t plen) {
+  int m = plen;
+  int n = tlen;
+
+  int* f = init_array(m); // Failure function values.
+  int i = 0;
+  int j = 0;
+
+  while (i < n) {
+    if (t[i] == p[j]) {
+      if (j == m - 1) {
+        return i - j;
+      }
+      else {
+        i += 1;
+        j += 1;
+      }
+    }
+    else {
+      if (j > 0) {
+        j = f[j-1];
+      }
+      else {
+        i += 1;
+      }
+    }
+  }
+
+  return -1;
+}
+
+void failure(char* p, int* f) {
+  f[0] = 0;
+  int i = 1;
+  int j = 0;
+
+  int m = strlen(p);
+
+  while (i < m) {
+    if (p[i] == p[j]) {
+      f[i] = j + 1; // j+1 matches up to the current character.
+      i += 1;
+      j += 1;
+    }
+    else if (j > 0) {
+      j = f[j - 1];
+    }
+    else {
+      f[i] = 0;
+      i += 1;
+    }
+  }
+}