Contiguous Recipe Lookup I
ingredients is an ordered list, and each recipe in recipes is an ordered list too. A recipe is found when it appears in ingredients as a contiguous run — every element in order, with nothing in between. An empty recipe always counts as found.
Return one boolean per recipe. Elements are numbers or strings and compare by value.
recipesFound([1, 2, 3, 4, 5], [[2, 3], [4, 5], [3, 5], [1], []])
-> [true, true, false, true, true]
recipesFound(["egg", "milk", "flour", "sugar"],
[["milk", "flour"], ["flour", "milk"], ["sugar"], ["egg", "milk", "flour", "sugar", "vanilla"]])
-> [true, false, true, false]Both lists can hold 200,000 entries, so checking each recipe against each position is too slow.
Hints
Hint 1
Scanning the ingredients once per recipe is O(n · recipes). Turn it around: scan the ingredients once and match every recipe at the same time.
Hint 2
Put all recipes in a trie and add failure links (Aho–Corasick): each ingredient advances one state, and the state's output list says which recipes just ended here.