// Knuth-Morris-Pratt algorithm
// copypasted from http://cprogramming.com/snippets/source-code/knuthmorrispratt-kmp-string-search-algorithm
char *kmp_search(char *haystack, size_t haystack_size, char *needle, size_t needle_size)
{
    int *T;
    int i, j;
    char *result = NULL;

    if (needle_size==0)
        return haystack;

    /* Construct the lookup table */
    T = (int*) malloc((needle_size+1) * sizeof(int));
    T[0] = -1;
    for (i=0; i<needle_size; i++)
    {
        T[i+1] = T[i] + 1;
        while (T[i+1] > 0 && needle[i] != needle[T[i+1]-1])
            T[i+1] = T[T[i+1]-1] + 1;
    }

    printf ("restarts table:\n");
    for (i=0; i<needle_size+1; i++)
        printf ("T[%d]=%d\n", i, T[i]);

    /* Perform the search */
    for (i=j=0; i<haystack_size; )
    {
        if (j>=0)
            print_compare (haystack, i, needle, j);
        if (j < 0 || haystack[i] == needle[j])
        {
            ++i, ++j;
            if (j == needle_size)
            {
                result = haystack+i-j;
                break;
            }
        }
        else
        {
            j = T[j];
            if (j==-1)
                printf ("Restarting needle at the beginning\n");
            else
                print_state_needle(needle, j);
        };
    }

    free(T);
    return result;
}