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

#define TRUE 1
#define FALSE 0

struct Pattern
{
    char const   * Pattern;
    unsigned int   Length;
    int          * Table;
};

char createPrefixTable( struct Pattern * pattern )
{
    int patternPos;       // Position im Pattern
    int partLength;       // Länge der Übereinstimmung

    pattern->Length = strlen( pattern->Pattern );

    pattern->Table = malloc( ( 1 + pattern->Length ) * sizeof( int ) );
    if( pattern->Table )
    {
        patternPos = 0;
        partLength = -1;

        pattern->Table[ 0 ] = -1;

        while( patternPos < pattern->Length )
        {
            while( partLength >= 0 && pattern->Pattern[ partLength ] != pattern->Pattern[ patternPos ] )
                partLength = pattern->Table[ partLength ];

            patternPos++;
            partLength++;
            pattern->Table[ patternPos ] = partLength;
        }

        return TRUE;
    }

    return FALSE;
}

int find( char const * text, unsigned int textLength, struct Pattern * pattern )
{
    int textPos = 0;
    int patternPos = 0;

    while( textPos < textLength )
    {
        while( patternPos >= 0 && text[ textPos ] != pattern->Pattern[ patternPos ] )
            patternPos = pattern->Table[ patternPos ];

        patternPos++;
        textPos++;

        if( patternPos == pattern->Length )
            return textPos - pattern->Length;
    }

    return -1;
}

int main()
{
    struct Pattern pat;
    char const * text = "abababcbaababcababcab";
    unsigned int textLength = strlen( text );

    pat.Pattern = "ababcabab";

    if( createPrefixTable( &pat ) )
    {
        int pos = 0;
        while( ( pos = find( &text[pos], textLength - pos, &pat )) >= 0 )
        {
          printf( "found '%s' at position %d\n", pat.Pattern, pos );
          pos ++;
        }

        free( pat.Table );
    }
    else
    {
        printf( "Could not create prefix table\n" );
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}