Stream of Characters

Letters of stream arrive one by one. After each letter, report whether some suffix of the letters received so far is one of the words.

For words = ["cd", "f", "kl"] and stream = "abcdefghijkl" the answer is [False, False, False, True, False, True, False, False, False, False, False, True].

The starter code tries every word after every letter. It is correct but too slow for many words and long streams.

Examples

Example 1

Input:

stream_checker(['cd', 'f', 'kl'], 'abcdefghijkl')

Output:

[False, False, False, True, False, True, False, False, False, False, False, True]

Example 2

Input:

stream_checker(['a'], 'ba')

Output:

[False, True]

Constraints

• 0 <= len(words) <= 2000
• 1 <= len(word) <= 10
• 0 <= len(stream) <= 100000
• Lower-case letters.