I was trying to solve a problem. Given a set of black and white intervals, select a smallest number of white intervals that collectively overlap every black interval.

I know it's greedy but can't exactly figure out why. Also, proving greedy is a little difficult. Can someone using greedy please prove it formally.

Thanks in advance!

Hi, I was trying to solve a problem which goes like this:

Given a list of N strings and another list of M strings, output the shortest string (of lower case English letters) that contains all N initiation words as substrings and none of the M forbidden words.If there are multiple answers, output any one of them. If there are no answers, output a “-” in a single line.

Constraints:

N ≥ 1, M ≥ 0, and 1 ≤ N + M ≤ 15.

The sum of the lengths of all strings in one test case does not exceed 320.

Somehow, I think this is related to Aho-Corasick but can't exactly figure out how. Need some direction here.

Thanks!

Hello, CF.

I was working on this problem. I know that this problem uses some variation of KMP to solve it. However I can't think of a linear time algorithm for it. Any help will be appreciated. Thanks.