int c,i,j,k,m,n,t; /* c is counter for character comparisons */
char pat[100], text[100];
int h[100];
/*****  This is to check a!=b. c is to count character comparisons ***/
int mismatch(char a, char b){
  c++; if(a!=b) return 1; else return 0;
}
/** This gives layouts for displaying trace of matching process ***/
out(int k){ int i;
  for(i=1; i<=j-k; i++)printf("  ");
  for(i=1; i<=m; i++)printf("%c ",pat[i]);
  printf("\n");
}
main(){
printf("input m "); scanf("%d", &m); getchar();
printf("input pat "); for(i=1; i<=m; i++) scanf("%c", &pat[i]);
getchar();
printf("input n "); scanf("%d", &n); getchar();
printf("input text "); for(j=1; j<=n; j++) scanf("%c", &text[j]);
for(i=1; i<=m; i++) printf("%c ", pat[i]); printf("\n");

/********   Computation of h  *****************/
t=0; h[1]=0;
for(i=2; i<=m; i++){
  while((t>0)&&(pat[i-1]!=pat[t])) t=h[t];
  t++;
  printf("i, t  %d %d  pat[i] pat[t] %c %c  ",i, t, pat[i], pat[t]);
  if (pat[i]!=pat[t])h[i]=t; else h[i]=h[t];
  for(j=1;j<=i;j++)printf("%d ",h[j]); printf("\n");
}

/******* Output h and text ****************/
for(i=1;i<=m; i++) printf("%d ",h[i]); printf("\n");
for(j=1; j<=n; j++) printf("%c ", text[j]); printf("\n");

/***** main matching starts ***********/
j=1; i=1; c=0; 
out(1);
while(i<=m && j<=n){
  while((i>0)&&mismatch(pat[i],text[j])){i=h[i]; out(i);}
  i++; j++;
}
  if (i>m)printf("found at %d\n", j-i+1);
  else printf("not found\n");
  printf("count= %d\n", c);
} /** end of main **/
/* sample session 
input m 7
input pat abbabbc
input n 17
input text abbabbabbaabbabbc
a b b a b b c

Each of the following lines is at the end of i-th iteration
i, t  2 1  pat[i] pat[t] b a  0 1
i, t  3 1  pat[i] pat[t] b a  0 1 1
i, t  4 1  pat[i] pat[t] a a  0 1 1 0
i, t  5 2  pat[i] pat[t] b b  0 1 1 0 1
i, t  6 3  pat[i] pat[t] b b  0 1 1 0 1 1
i, t  7 4  pat[i] pat[t] c a  0 1 1 0 1 1 4
0 1 1 0 1 1 4
a b b a b b a b b a a b b a b b c
a b b a b b c
      a b b a b b c
            a b b a b b c
                    a b b a b b c
found at 11
count= 20

abcabcb
aabcabcabcabcb
i, t  2 1  pat[i] pat[t] b a  0 1
i, t  3 1  pat[i] pat[t] c a  0 1 1
i, t  4 1  pat[i] pat[t] a a  0 1 1 0
i, t  5 2  pat[i] pat[t] b b  0 1 1 0 1
i, t  6 3  pat[i] pat[t] c c  0 1 1 0 1 1
i, t  7 4  pat[i] pat[t] b a  0 1 1 0 1 1 4
0 1 1 0 1 1 4
a a b c a b c a b c a b c b
a b c a b c b
  a b c a b c b
        a b c a b c b
              a b c a b c b
found at 8
count= 17

*/