KMP

Having started reading the Porat and Porat paper for their streaming pattern matching algorithm, it was made clear that these algorithms share a parentage of sorts in the KMP algorithm. for completeness I have read the details of the algorithm from their original paper. These streaming algorithms essentially 'shift' the (sub)pattern by it's period. This pecisesly what KMP does. The streaming algorithm has extra complexity of fingerprints, but as KMP ensures one never backtracks it clear to see why the streaming algorithms bear this striking resemblance.