The following implementation is written in C:
INPUT: Text T[0,n-1], Pattern P[0,m-1] Output alle matches of P in TInitNext(P); j=0; for (i=1;i<=n;i++) { while ((j>0) && (P[j+1] != T[i])) { j=next[j]; } if (P[j+1] == T[i]) j++; if (j == m-1) { print "Found P"; j = next[j]; } }
Procedure InitNext(P) Input: Pattern P
next[1] = 0; for (q=2;q<=m;q++) { while ((l>0) && (P[l+1] != P[q])) { l = next[l]; } if (P[l+1] == P[q]) l++; next[q] = l; }