I wonder if there is any algorithm to solve following problem in polynomial order of time :
You're given m strings named s, s, s, ..., s[m].
N is defined as size of input file ( s.size + s.size + s.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:
sample test 2:
UPD : With help of CNT0 the problem has been solved!
This problem's original name is "Shortest common supersequence" and it's NP-complete!