M.Mahdi's blog

By M.Mahdi, 4 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 CNT0 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  

»
4 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

  • »
    »
    4 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:".

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

    Could you please explain the solution?

    • »
      »
      »
      4 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 :(

      • »
        »
        »
        »
        4 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. :)

»
4 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.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 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.

  • »
    »
    4 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?

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

M.Mahdi Can you please provide your solution?