From b9899c6cbe2f694c9db36e9d4e15c532d10b546f Mon Sep 17 00:00:00 2001
From: Alexander Pickering <alexandermpickering@gmail.com>
Date: Thu, 25 Oct 2018 12:08:54 -0400
Subject: Started refactoring code

Added a src/ and build/ directory
Added a include/ directory
Included file is smaller
---
 src/kmp.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 src/kmp.c

(limited to 'src/kmp.c')

diff --git a/src/kmp.c b/src/kmp.c
new file mode 100644
index 0000000..d5923bf
--- /dev/null
+++ b/src/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;
+    }
+  }
+}
-- 
cgit v1.2.3-70-g09d2