diff options
| author | Alexander Pickering <alexandermpickering@gmail.com> | 2018-10-25 12:08:54 -0400 |
|---|---|---|
| committer | Alexander Pickering <alexandermpickering@gmail.com> | 2018-10-25 12:08:54 -0400 |
| commit | b9899c6cbe2f694c9db36e9d4e15c532d10b546f (patch) | |
| tree | 248564d6bd22dd6f11459a51f73a144ae91756fc /kmp.c | |
| parent | d416a80324225d0c64c5021e74773a2e768de73a (diff) | |
| download | libctemplates-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.c | 70 |
1 files changed, 0 insertions, 70 deletions
@@ -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; - } - } -} |
