/*
A Knuth-Morris-Pratt algorithm example
v 0.01b without debugging code
coder: Yuriy Grishin <grishin@minselhoz.samara.ru>
*/
#include <stdio.h>

int main(int argc, char *argv[])
{    
    char P[] = "ababababca";
    char T[] = "dsfvdsfbdasvasdvdfbdsvsdavasdvsd_ababamabca";
    int m = sizeof(P)/sizeof(P[0]) - 1; // length of P
    int n = sizeof(T)/sizeof(T[0]) - 1; // length of T
    int d[sizeof(P)/sizeof(P[0]) - 1] = {0};    
    int q = 0;
    int k = 0;
    int i = 0;
    
    //kmp pre
    d[0] = 0;
    for(q = 1; q < m; q++)
    {
        while(k > 0 && P[k] != P[q])
            k = d[k];
        if(P[k] == P[q])
            k++;
        d[q] = k;
    }

    //kmp
    q = 0;
    for(i = 0; i < n; i++)
    {
        while(q > 0 && P[q] != T[i])            
            q = d[q];
        if (P[q] == T[i])
            q++;
        if (q == m)
        {            
            printf("found at %d\n", i - m + 1);
            q = -1;
            break;
        }            
    }
    if (q != -1)
        printf("NOT found\n");
    scanf("%u", i);
    return 0;
}