aboutsummaryrefslogtreecommitdiff
path: root/kmp.c
diff options
context:
space:
mode:
authorAlexander Pickering <alexandermpickering@gmail.com>2018-10-25 12:08:54 -0400
committerAlexander Pickering <alexandermpickering@gmail.com>2018-10-25 12:08:54 -0400
commitb9899c6cbe2f694c9db36e9d4e15c532d10b546f (patch)
tree248564d6bd22dd6f11459a51f73a144ae91756fc /kmp.c
parentd416a80324225d0c64c5021e74773a2e768de73a (diff)
downloadlibctemplates-b9899c6cbe2f694c9db36e9d4e15c532d10b546f.tar.gz
libctemplates-b9899c6cbe2f694c9db36e9d4e15c532d10b546f.tar.bz2
libctemplates-b9899c6cbe2f694c9db36e9d4e15c532d10b546f.zip
Started refactoring code
Added a src/ and build/ directory Added a include/ directory Included file is smaller
Diffstat (limited to 'kmp.c')
-rw-r--r--kmp.c70
1 files changed, 0 insertions, 70 deletions
diff --git a/kmp.c b/kmp.c
deleted file mode 100644
index d5923bf..0000000
--- a/kmp.c
+++ /dev/null
@@ -1,70 +0,0 @@
-#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;
- }
- }
-}