#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 4096

char next[MAX];

/* i = Postion im Text */
/* j = Postion im Muster */
void kmpSearch(char *muster, char *text)
{
    int i=0, j=0;
    int m=strlen(muster);  /*Länge Muster*/
    int n=strlen(text);    /*Länge Text*/
    init_next(muster);     /* Tabelle für next berechnen*/

    while (i<n)    /*Solange wir nicht am Ende vom Text sind*/
    {
        while (j>=0 && text[i]!=muster[j]) j=next[j];
        i++; j++;
        if (j==m)
        {
             printf("Gefunden an Pos. %d\n",i-j);
             j=next[j];
        }
    }
}

void init_next(char *muster)
{
 int i, j, m=strlen(muster);
 next[0]=-1;
 for(i=0, j=-1; i<m; i++, j++, next[i]=j)
  while((j >=0) && (muster[i] != muster[j])) j=next[j];
}


int main()
{
 kmpSearch("ex", "a example text");

 return 0;
}