#include<stdio.h>

 #include<string.h>

 void makeNext(const char P[],int next[])

 {

     int q,k;

     int m = strlen(P);

     next[] = ;

     for (q = ,k = ; q < m; ++q)

     {

         while(k >  && P[q] != P[k])

             k = next[k-];

         if (P[q] == P[k])

         {

             k++;

         }

         next[q] = k;

     }

 }

 int kmp(const char T[],const char P[],int next[])

 {

     int n,m;

     int i,q;

     n = strlen(T);

     m = strlen(P);

     makeNext(P,next);

     for (i = ,q = ; i < n; ++i)

     {

         while(q >  && P[q] != T[i])

             q = next[q-];

         if (P[q] == T[i])

         {

             q++;

         }

         if (q == m)

         {

             printf("Pattern occurs with shift:%d\n",(i-m+));

         }

     }

 }

 int main()

 {

     int i;

     int next[]={};

     char T[] = "ababxbababcadfdsss";

     char P[] = "abcdabd";

     printf("%s\n",T);

     printf("%s\n",P );

     // makeNext(P,next);

     kmp(T,P,next);

     for (i = ; i < strlen(P); ++i)

     {

         printf("%d ",next[i]);

     }

     printf("\n");

     return ;

 }