Detect stop-token during streaming inference

Coding: Stop-token detection during streaming inference During LLM inference you receive a stream of generated token IDs. Given one or more stop sequences (each a list of token IDs), you must stop immediately when the suffix of the generated stream matches any stop sequence, and output the tokens before the stop sequence. Task Given: A generated token sequence tokens in order. K stop sequences (token ID lists, variable lengths). Output: If at some point the suffix matches any stop sequence for the first time, output the truncated tokens (excluding the stop sequence). Otherwise output the original tokens. Rules Stop sequences must match a contiguous sequence and occur at the end (suffix) of the current stream. With multiple stop sequences, stop as soon as any matches. Must support streaming: amortized O(1) or O(log M) per incoming token, where M is total stop length. I/O (stdin/stdout) Input: Line 1: T K Line 2: T token IDs Next K lines: each stop sequence as L s1 s2 ... sL Output: One line: truncated token IDs space-separated (empty line if none). Constraints 1 <= T <= 2e5, 1 <= K <= 2e5, sum(L) <= 2e5 Example Input 8 2 1 2 3 4 5 6 7 8 3 6 7 8 2 4 5 Output 1 2 3