coder_1560's blog

Strings Problem.
By coder_1560, history, 8 years ago, In English

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!

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Interesting problem.

Idea: Make 2^N similar Aho-Corasick trie graphs. mask-th graph means that you have already written words from this mask(i-th digit in 2-based numeral system equals 1 if you have written i-th word). You should find a path of least length that connect 0-graph and (2^N-1) graph. You have only 0-weighted(connect graphs) and 1-weighted(connect vertexes) edges. So you can use 0-1 bfs with O(|E|)=O(2^N * |trie| * 26) that should pass tests:)

In Aho-Corasick trie you should prohibit all jumps that lead to forbidden words.

Also you can solve this problem.

P.s. It is a good practice to share a link to your problem.

→ Reply