Knuth- Morris- Pratt Algorithm

Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a" word" W within a main" text string" S by utilizing the observation that when a mismatch happens, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. The algorithm was conceived by James H. Morris and independently observed by Donald Knuth" a few weeks later" from automata theory.

Knuth- Morris- Pratt source code, pseudocode and analysis