An interesting problem about String

Statement

Given strings. Find the string with minimum length such that each of given strings is a substring of .

Constraint

Every of strings has length not exceed

Example:

Input:

3
ab
ba
abb

Output:

abba

This problem is hard for me. Can you give me a hint? Thank you in advance.

• 7 hours ago, # ^ | I have successfully solved the easy version of it but hard version, I can't

  • 7 hours ago, # ^ | You can see that n = 10, so that's the hint that you're able to test every combination. However how to test every combination? A quick way is with string hashing

• 7 hours ago, # ^ | ← Rev. 2 →   0 Your solution is incorrect. Consider the test: 4 abc bcx xb axa Your program returns the string abcaxabcxb, while a considerably shorter string axabcxb contains all the substrings, too.

  • 7 hours ago, # ^ | yes, you are right. I modified the code and used SCS. thx

    • 7 hours ago, # ^ | ← Rev. 2 →   0 Your solution is still incorrect, though it performs a bit better on trivial tests. Consider the test: 4 aaa cae aec eee Your solution returns the string aaacaeceee, while the string aaaecaeee is shorter, but also contains all the substrings. If you look at my other comment, you'll understand, that designing an exact polynomial algorithm for this problem is in principle very hard.

• 4 hours ago, # ^ | Thank you

• 3 hours ago, # ^ | ← Rev. 2 →   0 Can't it be done by creating a suffix automaton? We can do something sort of topological sorting on the trie having suffix links(or failure links) and then start creating the final string which we need using dfs?

  • 32 minutes ago, # ^ | ← Rev. 2 →   0 That wouldn't always be an optimal solution. Indeed, there's a conjecture that a variation of the algorithm you suggested 2-approximates the solution. By the way, trie with suffix links is basically Aho-Corasick automaton. And it makes sense that it's possible to construct a solution with such a structure: think about it -- the Aho-Corasick algorithm basically checks character-by-character, that all the substrings are present in our string.