Michael Weber: Random Bits and Pieces

Lisp Logo (by Conrad Barsky)

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 to DO-DELIMITED-STREAM.