Keyword Alarm on a Character Stream

Design a class KeywordAlarm that watches characters arriving one at a time and raises an alarm as soon as the text received so far ends with one of the keywords:

• KeywordAlarm(keywords): the list of keywords (non-empty lowercase strings, may contain duplicates or an empty list).
• feed(ch) appends the single character ch to the stream and returns True if some keyword is a suffix of the whole stream so far, else False.

Examples

ops:  ["KeywordAlarm", "feed", "feed", "feed", "feed", "feed", "feed"]
args: [[["abc", "xy"]], ["a"], ["b"], ["c"], ["x"], ["y"], ["z"]]
Output: [None, False, False, True, False, True, False]
Explanation: after "abc" the stream ends with "abc"; after "abcxy" it ends with "xy".

Constraints

• 0 <= len(keywords) <= 2000, total keyword characters <= 2 * 10**5, longest keyword L <= 200
• Up to 10**4 calls to feed
• Target: O(L) per feed; rescanning the whole stream, or every keyword, per character is too slow

Goals

• Build a trie of reversed words so suffix questions become prefix walks
• Bound the work per character by the longest keyword