#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;
    }
  }
}