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

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

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
  • Проголосовать: не нравится

»
11 лет назад, # |
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

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Are u sure it is O(NlogN) :)

    You may want to write "EDIT:".

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Could you please explain the solution?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 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 :(

      • »
        »
        »
        »
        11 лет назад, # ^ |
        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. :)

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

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

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

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

»
11 лет назад, # |
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.

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

M.Mahdi Can you please provide your solution?