949. Stream of Characters (Aho-Corasick Lite)

Given a dictionary of words and a stream of characters, after each character report whether some word from the dictionary is a suffix of the characters seen so far. Return the boolean answers in order as an array. The input is JSON {words, stream}.

Input: JSON {words, stream}.

Output: Array — a boolean per streamed character.

Examples

Input: {"words":["cd","f","kl"],"stream":"abcdefghijkl"}
Output: [false,false,false,true,false,true,false,false,false,false,false,true]
Explanation: Matches after 'd', 'f', and 'l'.

Input: {"words":["a"],"stream":"aa"}
Output: [true,true]
Explanation: Each 'a' matches.

Input: {"words":["xyz"],"stream":"abc"}
Output: [false,false,false]
Explanation: No matches.

Constraints

• 1<=words<=2000
• 1<=stream length<=4*10^4

Asked by