Apply ordered token merges to a string

Many language models read text as a list of token ids. In this scheme, every token after the single characters is built from two earlier tokens, and turning text into ids means applying those merges in order.

Implement:

def tokenize(text: str, alphabet: list[str]) -> list[int]

A token's id is its index in alphabet.

• Start. The first entries of alphabet are single characters, one per distinct character. Every entry after them has two or more characters. Replace each character of text with the id of its single-character token. Raise ValueError if a character has no token.
• Merges. Go through the multi-character tokens in alphabet order. For token t with id i, scan the current id sequence left to right. Wherever two adjacent ids x, y spell t (alphabet[x] + alphabet[y] == t), replace the pair with i and continue scanning after the new token. Matches do not overlap.
• A token may split into two earlier tokens in more than one way; any such split counts. A token that cannot be written as two earlier tokens never matches and is skipped.
• Return the id sequence after the last token has been processed.

Example 1

text = "abcab", alphabet = ["a", "b", "c", "ab", "bc", "abc", "cab"]

Result: [5, 3].

Example 2

text = "aaa", alphabet = ["a", "aa"] returns [1, 0]. The scan is left to right and matches do not overlap.

Constraints

• 0 <= len(text) <= 10^5; 1 <= len(alphabet) <= 10^4; entries are distinct and at most 32 characters long.
• Start with a straightforward solution, then make it fast when most merges touch only a small part of the text. State the time and space complexity.

Reconstructed from the reported question; details may differ from what interviewers ask.