Tokenize Text with Dictionary Using Longest Match

Problem: Tokenize Text with a Dictionary Using Longest Match You are given a string text and a dictionary. Each dictionary entry has the format: key:id where key is a token string that can be matched in text, and id is the identifier for that token. Scan text from left to right and tokenize it: At the current position, if one or more dictionary keys match a prefix of text starting at this position, choose the longest key. Output the corresponding id, and advance by len(key) characters. If no key matches at the current position, output the original character at that position and advance by 1. Repeat until the entire text is processed. Return the resulting token sequence. For judging purposes, output the token sequence as a JSON array of strings. Input Format n key1:id1 key2:id2 ... keyn:idn text n is the number of dictionary entries. The next n lines each contain one key:id entry. The last line is the input text. Output Format Output a JSON array of strings representing the tokenized result. Constraints 0 <= n <= 10^5 0 <= len(text) <= 10^5 1 <= len(key) <= 1000 id is a non-empty string. Assume the same key will not appear with multiple different ids. Example 1 Input: 3 hello:T_HELLO hell:T_HELL world:T_WORLD helloworld Output: ["T_HELLO", "T_WORLD"] Explanation: At position 0, both hell and hello match, so choose the longest one, hello. Example 2 Input: 2 ab:X abc:Y zabcd Output: ["z", "Y", "d"] Example Input 3 hello:T_HELLO hell:T_HELL world:T_WORLD helloworld Output ["T_HELLO", "T_WORLD"]