albeXL's blog

Shortest Common Superstring
By albeXL, history, 7 years ago, In English

Can someone help me solve this problem? Given N <= 16 strings I need to find the shortest(in length) string that contains all N strings as a substring, in case of a tie I need to find the smallest one in lexicographic order. Thanks in advance

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

And what about length of the strings?

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Depending on lengths of the strings this can be the same or an easier version of : http://mirror.codeforces.com/problemset/gymProblem/101064/E

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

length of strings is at most 100

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Construct an Aho-Corasick automaton and do a BFS for find the shortest path that goes through every final state.

→ Reply