M.Mahdi's blog

Shortest Covering String (SCS)
By M.Mahdi, 11 years ago, In English

Hi :)
I wonder if there is any algorithm to solve following problem in polynomial order of time :

You're given m strings named s[1], s[2], s[3], ..., s[m].
N is defined as size of input file ( s[1].size + s[2].size + s[3].size + ... + s[m].size).
Print a single string with the smallest size (call it ans!) that holds following condition :
For any i, (1 <= i <= m) s[i] can be obtained from ans:
We'll say that string s can be obtained from string t, if we can remove some characters from string t and have a result that is string s.

sample test 1:

input :
aba
bab
output :
abab

sample test 2:

input :
maskh
are
output :
maskhre

UPD : With help of CountZero the problem has been solved!
This problem's original name is "Shortest common supersequence" and it's NP-complete!

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

»
11 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

No there isn't. It is an NP hard problem and you can solve this in O((2^N)*N) time complexity with bitmask DP. http://lightoj.com/volume_showproblem.php?problem=1073

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Are u sure it is O(NlogN) :)

    You may want to write "EDIT:".

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Could you please explain the solution?

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

      Naive solution is O(N!). But you can use bitmask DP to reduce this complexity to O((2^N)*N). If you know bitmask you can do this. But my english is not sufficient to explain this algorithm , sorry :(

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        well , i realy sorry for saying this , this blog is abouth subsequence not substrings like lightoj problem 1073 but maybe there is a solution with bitmask. i didnt thinked abouth it. :)

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

Oh sorry , my mistake :( Please forgot all my comments , in this post. I misunderstand this question.

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

So this problem is still unsolved ... Any idea?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

A related problem: http://ipsc.ksp.sk/2013/practice/problems/r.html

"Solution" (it says the exact solution is unknown): http://ipsc.ksp.sk/2013/real/solutions/booklet.pdf

So I guess your problem is NP-hard.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Thanks!
    BTW, could you link it to a proven NP-hard problem?

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

http://en.wikipedia.org/wiki/Shortest_common_supersequence http://en.wikipedia.org/wiki/List_of_NP-complete_problems

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

M.Mahdi Can you please provide your solution?

→ Reply