#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <assert.h>

void print_n_spaces (int n)
{
        for (int i=0; i<n; i++)
                putchar(' ');
};

void print_compare (char *haystack, unsigned i, char *needle, unsigned j)
{
        printf ("going to compare: %s\n", haystack);
        printf ("                  ");
        print_n_spaces (i-j);
        printf ("%s\n", needle);
        printf ("                  ");
        print_n_spaces ((i-j)+j);
        printf ("^\n");
};

void print_state_needle(char *needle, int j)
{
        assert(j>=0);
        printf ("Restarting needle at: %s\n", needle);
        printf ("                      ");
        print_n_spaces (j);
        printf ("^\n");
};

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

void main()
{
	char *haystack="eex eel";
	char *needle="eel";
	kmp_search(haystack, strlen(haystack), needle, strlen(needle));
};