Stack Trace Suffix Matching

Problem: Stack Trace Suffix Matching You are maintaining a crash diagnosis system. The system stores several known complete stack traces. Each stack trace consists of frames ordered from the entry point of the call chain to the final crashing frame. Now the system receives incomplete crash reports. Due to collection limitations, a report may only contain the last few frames of the stack trace, i.e. a suffix close to the crash point. For each query stack trace, return all known trace_ids such that the last k frames of the known trace are exactly equal to the k frames in the query. If no known trace matches, output UNKNOWN. Input Format N trace_id_1 K_1 frame_1 frame_2 ... frame_K1 trace_id_2 K_2 frame_1 frame_2 ... frame_K2 ... trace_id_N K_N frame_1 frame_2 ... frame_KN Q M_1 frame_1 frame_2 ... frame_M1 M_2 frame_1 frame_2 ... frame_M2 ... M_Q frame_1 frame_2 ... frame_MQ N: number of known stack traces. Each known trace has a unique string trace_id. K_i: number of frames in that known trace. Q: number of queries. M_j: number of frames in the j-th query. Frame names do not contain spaces. Output Format For each query, print one line: If there are matches, print all matching trace_ids in lexicographical order, separated by a single space. Otherwise, print UNKNOWN. Constraints 1 <= N, Q <= 2 * 10^5 The total number of frames across all known stack traces is at most 2 * 10^5. The total number of frames across all queries is at most 2 * 10^5. 1 <= K_i, M_j trace_ids are unique. Example Input: 3 A 4 main api parse fail B 3 worker parse fail C 3 main db fail 5 2 parse fail 3 api parse fail 1 fail 2 db fail 2 main fail Output: A B A A B C C UNKNOWN Example Input 3 A 4 main api parse fail B 3 worker parse fail C 3 main db fail 5 2 parse fail 3 api parse fail 1 fail 2 db fail 2 main fail Output A B A A B C C UNKNOWN