Longest-Match Tokenization with UNK and Optional UNK-Run Compression

You are given a string text and a vocabulary map vocab: vocab maps token strings to integer ids. vocab always contains a special token "UNK" whose id is some integer (e.g. -1). Implement tokenize(text, vocab) that scans text from left to right and performs longest-match tokenization (a.k.a. maximal munch), returning a list of token ids. Rules: At position i, if there exists any token in vocab (excluding "UNK") that exactly matches text[i:j], choose the match with the maximum length (j - i), output its id, and set i = j. If no non-"UNK" token matches at position i, output vocab["UNK"] and advance i by 1. Optional follow-up: if the output contains consecutive UNK ids (e.g. -1,-1,-1), compress them into a single UNK (e.g. -1). Discuss time complexity and any optimization you apply (e.g. limiting attempts by the maximum token length). Constraints (for complexity design): 1 <= len(text) <= 1e5 1 <= |vocab| <= 1e5 maximum token length L can be up to 1e3 Examples: vocab = {"app": 1, "apple": 2, "UNK": -1} "apple" -> [2] "bbb" -> [-1, -1, -1] (or [-1] with compression) "appbbbapp" -> [1, -1, 1] (with compression the middle run becomes a single -1) "appleappleapple" -> [2,2,2] Example Input apple 3 app 1 apple 2 UNK -1 0 Output 2