#P1770. Bold Key Phrases

    ID: 15055 Type: Default 1000ms 256MiB

Bold Key Phrases

Bold Key Phrases

You are given two lines of input. The first line is the keyword string, and the second line is the text string. Both strings consist of pinyin representations of Chinese characters, spaces (which separate each character) and half‐width punctuation. A valid phrase (词语) is defined as a contiguous sequence of at least two Chinese characters (i.e. at least two tokens). From the keyword string, extract all possible phrases (all contiguous token subsequences with length ≥ 2). Then, for each occurrence of any of these phrases in the text string, wrap that occurrence with a bold tag by inserting a <b> before the phrase and a </b> after the phrase. When bold regions overlap or touch, they must be merged so that the total number of tag pairs is minimized and the distance between any two tags is as short as possible.

For example, if the keyword is 'tao tao' and the text is 'tao tao, zhai ping guo!', then since the only phrase extracted from the keyword is "tao tao", the output should be <b>tao tao</b>, zhai ping guo!.

inputFormat

The input consists of two lines:

Line 1: A keyword string containing tokens (pinyin words) separated by spaces and may include half-width punctuation. Line 2: A text string in the same format where occurrences of phrases will be bolded.

outputFormat

Output a single line: the modified text string with <b> and </b> tags added around each occurrence of any phrase (contiguous sequence of at least two tokens) from the keyword string that appears in the text. Overlapping or contiguous bold intervals must be merged.

sample

tao tao
tao tao, zhai ping guo!
tao tao, zhai ping guo!