Contiguous Recipe Lookup II
All recipes are known up front, but the ingredients arrive as a stream that is too large to store: stream is an iterator you can read from front to back exactly once. Return one boolean per recipe — whether it appears somewhere in the stream as a contiguous run. An empty recipe always counts as found.
recipesInStream(stream of [1, 2, 3, 2, 3, 4], [[2, 3], [3, 4], [4, 5], []])
-> [true, true, false, true]
recipesInStream(stream of ["egg", "milk", "flour", "milk", "flour", "sugar"],
[["milk", "flour"], ["flour", "sugar"], ["egg", "sugar"]])
-> [true, true, false]Memory may grow with the total size of the recipes, not with the stream.
Hints
Hint 1
Everything the matching needs about the past is one state in an automaton built from the recipes, so nothing read so far has to be kept.
Hint 2
Build the Aho–Corasick automaton before touching the stream; then each element is one transition plus the outputs of the state it lands on.