Greedy longest-match tokenizer

Implement a greedy longest-match tokenizer.

You are given a string text and a list dictionary. Each entry has the form "<key>:<id>". key is a non-empty token string and id is its identifier. The key may itself contain :, but the id never does, so the id is everything after the last colon.

Write tokenize(text: str, dictionary: List[str]) -> List[str] that scans text from left to right and returns the ids of the tokens it produces:

• At the current position, find every key that starts there and choose the longest one. Emit its id and move past it.
• If no key starts at the current position, emit "[UNK]" for that single character and move forward by one.
• If the same key appears more than once in dictionary, use the first id.
• Raise an error for a malformed entry (no colon, empty key or empty id).

Matching is case-sensitive. text may be empty.

Constraints: 0 <= len(text) <= 10^5, up to 10^4 dictionary entries, each key at most 50 characters.

Example 1

text = "catalog"
dictionary = ["cat:10", "catalog:11", "a:12", "log:13"]
output = ["11"]

catalog is longer than cat, so it wins at index 0.

Example 2

text = "cats!"
dictionary = ["cat:10", "s:14", "c:15"]
output = ["10", "14", "[UNK]"]

cat beats c, then s matches, and ! has no key.

Aim for better than trying every substring length with slicing at each position. State the time complexity of your solution.