### M.Mahdi's blog

By M.Mahdi, 5 years ago, ,

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.

input :
aba
bab
output :
abab

#### sample test 2:

input :
are
output :

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

•
• +3
•

 » 5 years ago, # | ← Rev. 2 →   +13 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 Are u sure it is O(NlogN) :)You may want to write "EDIT:".
•  » » 5 years ago, # ^ |   +1 Could you please explain the solution?
•  » » » 5 years ago, # ^ |   0 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 :(
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 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. :)
 » 5 years ago, # |   +1 Oh sorry , my mistake :( Please forgot all my comments , in this post. I misunderstand this question.
 » 5 years ago, # |   +1 So this problem is still unsolved ... Any idea?
 » 5 years ago, # | ← Rev. 2 →   +1 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.pdfSo I guess your problem is NP-hard.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +1 Thanks! BTW, could you link it to a proven NP-hard problem?
 » 5 years ago, # |   +2
•  » » 5 years ago, # ^ |   +1 TnQ a lot!
 » 6 months ago, # |   -10 M.Mahdi Can you please provide your solution?