Блог пользователя M.Mahdi

Автор M.Mahdi, 13 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
← 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

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
13 лет назад, скрыть # |
← 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.pdf

So I guess your problem is NP-hard.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

M.Mahdi Can you please provide your solution?