Блог пользователя albeXL

Автор albeXL, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

And what about length of the strings?

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

length of strings is at most 100

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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