#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "kmp.h"

static int* prefix = NULL;
static int max_size = 0;

static void GetPrefixValue(const char* strPattern, int iPatternLen)
{
    if (iPatternLen>max_size) {
        prefix = (int*)realloc(prefix, iPatternLen*sizeof(int));
        max_size = iPatternLen;
    }
   
    int i, j; /* i runs through the string, j counts the hits*/
    i = 1; j = 0;
    prefix[0] = 0;
   
    while(i<iPatternLen)
    {
        if(strPattern[i] == strPattern[j])
        {
            prefix[i] = ++j;
        }
        else
        {
            j = 0;
            prefix[i] = j;
        }
       
        i++;
    }
}

static int KMPStringMatch(const char* strPattern, int iPatternLen, const char* strTarget, int iTargetLen)
{
int j =0;
int i;
for (i=0;i<iPatternLen;i++) {
while ((strPattern[i] != strTarget[j]) && (j > 0))
j = prefix[j-1];
if (strPattern[i] == strTarget[j])
j++;
if (j == iTargetLen)
return i - j + 1;
}
return -1;
}

int KMP(const char* strPattern, int len, const char* strTarget)
{
GetPrefixValue(strPattern, len);
return KMPStringMatch(strPattern, len, strTarget, strlen(strTarget));
}

void KMP_end()
{
free(prefix);
prefix=NULL;
max_size=0;
}