Strings Problem.

Revision en5, by coder_1560, 2017-03-09 12:02:36

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English coder_1560 2017-03-09 12:02:36 113
en4 English coder_1560 2017-03-09 12:01:28 499
en3 English coder_1560 2017-02-24 18:03:17 0 Tiny change: ' problem. My approa' -> ' problem. My approa'
en2 English coder_1560 2017-02-24 18:02:22 36 Tiny change: '.pdf.html). For the ' -> '.pdf.html) problem. My approach was to use KMP. For the '
en1 English coder_1560 2017-02-24 06:49:54 252 Initial revision (published)