Longest-Match Greedy Tokenization With Dictionary Replacement

Problem: Longest-Match Greedy Tokenization With Dictionary ID Replacement Given a text string text and a dictionary mapping token -> id (e.g., {"key": 123, "hello": 7}), process the text from left to right and produce an output string: At position i, find all dictionary tokens that match a prefix of text[i:]. If there is at least one match, choose the token with the maximum length (longest match), append its corresponding id (as a string) to the output, and advance i by len(token). If there is no match, append the single character text[i] to the output unchanged, and advance i by 1. Return/print the final output string. I/O format Input: Line 1: string text Line 2: integer n (number of dictionary entries) Next n lines: token id separated by a space (token contains no spaces) Output: One line: the resulting string Constraints 1 <= len(text) <= 2 * 10^5 1 <= n <= 2 * 10^5 Tokens contain no spaces. If multiple tokens match, you must pick the longest one. Example text = "abcxyz", dict = {"a":1, "abc":9, "xy":5} -> output "95z". Example Input abcxyz 3 a 1 abc 9 xy 5 Output 95z