Greedy Longest-Match Tokenization of a String Against a Fixed Vocabulary

A tokenizer splits text into tokens drawn from a fixed vocabulary. You are given a string `text` and a list `vocab` of distinct, non-empty strings. The token ID of `vocab[i]` is `i`. Tokenize `text` with the **greedy longest-match** rule: start at the beginning of `text`; at the current position, choose the longest vocabulary string that `text` continues with at that position, emit its token ID, and move the position forward by that string's length. Repeat until the whole of `text` has been consumed. Return the list of emitted token IDs, in order. ### Function Signature ```python def longest_match_tokenize(text: str, vocab: list[str]) -> list[int]: ``` ### Rules - The choice at each position is always the longest matching vocabulary string, even when a different choice would produce fewer tokens overall. - Because vocabulary strings are distinct, the longest match at a position is unique, so the output is uniquely determined. - Matching is exact and case-sensitive; spaces and punctuation are ordinary characters. ### Constraints - `1 <= len(text) <= 100000` - `1 <= len(vocab) <= 10000` - `1 <= len(vocab[i]) <= 50` for every `i`, and the total length of all vocabulary strings is at most `200000`. - All vocabulary strings are distinct. - `text` and every vocabulary string consist of printable ASCII characters (character codes 32 to 126 inclusive). - Every character that occurs in `text` is also present in `vocab` as a single-character string, so tokenization never gets stuck. - The output has between `1` and `len(text)` token IDs, each in the range `0` to `len(vocab) - 1`. ### Examples **Example 1** - Input: `text = "abcab"`, `vocab = ["a", "b", "c", "ab", "abc"]` - Output: `[4, 3]` - Explanation: At position 0 the candidates are `"a"`, `"ab"` and `"abc"`; the longest is `"abc"` (ID 4). At position 3 the candidates are `"a"` and `"ab"`; the longest is `"ab"` (ID 3). **Example 2** - Input: `text = "abcd"`, `vocab = ["a", "b", "c", "d", "ab", "bcd"]` - Output: `[4, 2, 3]` - Explanation: At position 0 the longest match is `"ab"`, leaving `"cd"`, which is tokenized as `"c"` then `"d"`. The split `"a"` + `"bcd"` would use only two tokens, but greedy longest-match never looks ahead. **Example 3** - Input: `text = "to be"`, `vocab = [" ", "b", "e", "o", "t", "to", "be", " b"]` - Output: `[5, 7, 2]` - Explanation: `"to"` (ID 5) is the longest match at position 0, `" b"` (ID 7) beats `" "` at position 2, and `"e"` (ID 2) remains.