Tokenize text by greedy longest dictionary match

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.

Clarifying questions

• If the same key appears twice, is a later entry with a different id an error or silently ignored?
• Can the text contain characters outside ASCII, and should [UNK] cover one code point?
• Should a key that is an empty string after splitting on the last colon raise, as with ":5"?
• Is the dictionary built once and reused for many texts, so it is worth preprocessing?

What a strong answer covers

• Parses each entry with rsplit(":", 1), validates it, and keeps the first id for each key.
• Builds a trie from the keys. At each position it walks the trie as far as the text allows and remembers the last node that ended a key, then emits that id and jumps past it, or emits [UNK] and moves one character.
• States the time: O(len(text) * L) where L is the longest key (at most 50), plus O(total key length) to build the trie, with no substring copies.
• Mentions the simpler alternative, a set of keys and a check of lengths from longest to shortest at each position, and why its slicing costs more.
• Tests: both examples, empty text, keys that contain :, duplicate keys, a text with no matching keys, and a key that is a prefix of a longer key that fails to match ("cata" with keys cat and catalog).

Follow-ups

• Choose the split with the fewest tokens instead of greedy longest-match (a dynamic program over positions).
• Map the ids back to text, and handle [UNK] characters losslessly.
• Process a very long stream without holding all of it in memory.
• Use Aho-Corasick to find every key occurrence in one pass.