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!

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

Are u sure it is

`O(NlogN)`

:)You may want to write "EDIT:".

Could you please explain the solution?

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 :(

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. :)

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

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

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.

Thanks!

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

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

TnQ a lot!

M.Mahdi Can you please provide your solution?