Andreas Fuchs wrote a visualization tool for string search. I could not resist to add the Knuth-Morris-Pratt algorithm, given that it was just a handful code for the algorithm itself, the visualization then comes for free, thanks to Andreas' preparatory work.
That reminded me, however, that I have a KMP implementation lying around. The KMP algorithm is easy to implement, and works well with streams:
KMP> (with-input-from-string (s "12345AaAaB67890") (let ((ts (make-array 10 :element-type 'character :adjustable t :fill-pointer 0))) (do-delimited-stream ((token expected (read-char s) (multiple-value-call #'values ts (read-line s nil))) "AAB" ; restart-vector generated automatically :predicate #'char-equal) (vector-push-extend token ts) (format *trace-output* "~&Expected ~A, got ~A" expected token)))) Expected A, got 1 Expected A, got 2 Expected A, got 3 Expected A, got 4 Expected A, got 5 Expected A, got A Expected A, got a Expected B, got A Expected B, got a Expected B, got B "12345AaAaB" "67890" T KMP>
KMP works in a way that it does not have to backtrack on the stream after a partial match, unlike a naïve algorithm. Neither does it store parts of the stream.
I used it to read from a stream until the given delimiter is
reached, and save everything upto and including the delimiter for
further processing. Since it does not seize control of the stream
I can, for example, process escape sequences or skip parts of the
stream, before I hand stream elements