KMP

/*
 * Algorithm : Knuth Morris Pratt
 *             String Matching
 * Complexity : O( N )
 * Note : 0 base indexing
 */
#define MAX 100007
long F[MAX+7];// keep longest prefix length of i length suffix
void failure_function( char *pattern, long len ){
    F[0] = F[1] = 0;
    long i,j;
    for( i=2;i<=len;i++ ){
        j = F[i-1];
        while( 1 ){
            if( pattern[j] == pattern[i-1] ){ F[i] = j + 1; break; }
            if( j==0) { F[i] = 0; break; }
            j = F[j];
        }
    }
}
void KMP( char *text, long len_t, char *pattern, long len_p  ){
    failure_function( pattern, len_p );
    long i = 0,j = 0;
    while( j<len_t ){
        if( text[j] == pattern[i] ) {
            i++;j++;
            if( i == len_p ) ;// match found
        } else if( i > 0 ) i = F[i];
        else j++;
    }
}