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

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.

Greedy Longest-Match Tokenizer

Hints

1. Checking every vocabulary string at every position is too slow when both text and vocab are large. Many vocabulary strings share prefixes; look for a structure that tests all strings with a common prefix in one pass.
2. When you follow characters of text forward from the current position, the walk can go past the end of a valid vocabulary string and then fail. Keep track of the most recent point where a complete vocabulary string ended.
3. No vocabulary string is longer than 50 characters, so the work done at each position is bounded by a small constant.

Approach

Insert every vocabulary string into a trie and mark the node where vocab[i] ends with its ID i. Then scan text left to right. From the current position, walk the trie one character of text at a time; whenever the walk reaches a node that ends a vocabulary string, record that ID and the position just after it. Stop when the next character has no matching child (or text ends). The last recorded ID is the longest vocabulary string that starts at the current position, because the walk visits the matching strings in increasing length. Emit it and jump to the recorded end position. The walk must remember the last complete match rather than the deepest node reached: for text "abcdx" with vocab containing "ab" and "abcde" but not "abcd", the walk reaches "abcd" and fails, so the answer at that position is "ab". Since every character of text is a single-character vocabulary string, at least one match always exists and the position always advances. Building the trie costs O(S) for total vocabulary length S, and each walk is at most 50 steps long, so tokenization costs O(n * L) with L <= 50.

• Time complexity: O(S + n * L), where S is the total length of the vocabulary strings, n = len(text), and L <= 50 is the longest vocabulary string
• Space complexity: O(S + n) for the trie and the output list