## Knuth–Morris–Pratt Algorithm (KMP)

Knuth–Morris–Pratt algorithm is the most popular linear time algorithm for string matching. It is little difficult to understand and debug in real time contests. So most programmer’s have a precoded KMP in their kitty.

To understand the algorithm, you can either read it from Introduction to Algorithms (CLRS) or from the wikipedia page. Here’s a sample C++ code.

void preKMP(string pattern, int f[]) { int m = pattern.length(),k; f[0] = -1; for (int i = 1; i<m; i++) { k = f[i-1]; while (k>=0) { if (pattern[k]==pattern[i-1]) break; else k = f[k]; } f[i] = k + 1; } } bool KMP(string pattern, string target) { int m = pattern.length(); int n = target.length(); int f[m]; preKMP(pattern, f); int i = 0; int k = 0; while (i<n) { if (k==-1) { i++; k = 0; } else if (target[i]==pattern[k]) { i++; k++; if (k==m) return 1; } else k=f[k]; } return 0; }

NJOY!

-fR0DDY

Advertisements

You could have handled the negative sign by setting the value of the precomputed array at position 0 equal to 0

ronziiJuly 13, 2011 at 2:57 PM