Tag Matching and Annotation with Pattern Priority

Problem: Annotate Text Substrings by Pattern Tags You are given a string text and a list of tagged patterns. Find all occurrences of the patterns in the text and annotate the selected substrings with their corresponding tags. Each pattern contains: tag: the label associated with this pattern; priority: an integer. A larger value means higher priority; pattern: the exact string to match. It may contain spaces. Matching rules: Matching is case-sensitive and exact. The same pattern may appear multiple times in the text, and every valid occurrence should be considered. Scan the text from left to right. If multiple patterns match at the current position: choose the one with the highest priority; if tied, choose the longer pattern; if still tied, choose the pattern that appeared earlier in the input. Once a pattern is selected at the current position, output that annotation and skip all characters covered by it. Output annotations must not overlap. If no pattern matches at the current position, move to the next character. For example, if the patterns are: San Francisco San Francisco and the text contains San Francisco, then with equal priority it should be matched as the whole phrase San Francisco, instead of two separate matches San and Francisco. Input Format text m tag_1<TAB>priority_1<TAB>pattern_1 tag_2<TAB>priority_2<TAB>pattern_2 ... tag_m<TAB>priority_m<TAB>pattern_m <TAB> denotes a tab character. A pattern may contain spaces. Output Format Print all selected annotations, one per line: start<TAB>end<TAB>tag<TAB>matched_substring Where: start is the 0-based start index; end is the exclusive end index; tag is the selected tag; matched_substring is the original substring from text. If there is no match, print: NONE Constraints 0 <= len(text) <= 10000 0 <= m <= 5000 1 <= len(pattern_i) <= 1000 sum(len(pattern_i)) <= 100000 priority_i is a signed 32-bit integer Example Input: San Francisco is in California 3 CITY_PART 5 San CITY_PART 5 Francisco CITY 5 San Francisco Output: 0 13 CITY San Francisco Example Input San Francisco is in California 3 CITY_PART 5 San CITY_PART 5 Francisco CITY 5 San Francisco Output 0 13 CITY San Francisco