Knuth-Morris-Pratt algorithm implemented in python .
neat stuff that's too small or self-explanatory to deserve its own web page.
This is a direct translation of the KMP algorithm in the book "Introduction to Algorithms" by Cormen, Lieserson, and Rivest.
See that book for an explanation of why this algorithm works.
It's pretty cool. The only things changed were some offsets, to cope with the fact that Python arrays are 0-offset.