Geek Answers Handbook

Build back the original string

I ran into an interesting Strings problem but couldn't solve it. Suppose we are given N lines of each of 3 characters, we need to build a line of length N + 2, such that it contains all the above lines as substrings. If the solution does not exist, type “-1” Can someone help me in resolving this issue?

+4
source share
2 answers

My answer is similar in nature to Pham Trung one , but I decided to build another schedule for which the problem can be solved effectively.

  • First, note that each of these parts must appear exactly once in our result. There are Nfragments and Nplaces where they may appear. When all these figures are different, it should be a bijection (one-to-one correspondence). When some of them are the same, the operator is not clear, but it can be assumed that we still have to place each part exactly as many times as it happens in the input.

  • , 2 ( , ) . & alpha; & beta; & gamma; , & alpha; & beta; & beta; & gamma;. : N arcs, . : , . .

+4

, N + 2, 3, , , ith (i +1)th, 2 .

, , N- N , (a,b), node a - node b.

NP- .

, N ( 10) , N dynamic programming with bitmask N <= 17.

(DAG), , , .

+3

More articles:


All Articles