Nicksil

# File: KnuthMorrisPratt.py
# Author: Keith Schwarz ([email protected])
#
# An implementation of the Knuth-Morris-Pratt (KMP) string-matching algorithm.
# This algorithm takes as input a pattern string P and target string T, then
# finds the first occurrence of the string T in the pattern P, doing so in time
# O(|P| + |T|).  The logic behind the algorithm is not particularly complex,
# though getting it to run in linear time requires a few non-obvious tricks.
#
# To motivate KMP, consider the naive algorithm for trying to match a pattern