You are not logged in. Please login at www.codechef.com to post your questions!

×

MIKE AND STRINGS

http://codeforces.com/contest/798/problem/B .. in this question , can somebody please explain how to find the minimum number of moves to make the two strings equal . for example - "ozozizc" and "zcozozi" .... thanks in advance

asked 22 Apr '17, 10:34

abhsh12345's gravatar image

1★abhsh12345
2413
accept rate: 20%

1

You can find the editorials here http://codeforces.com/blog/entry/51652

(22 Apr '17, 12:28) only44★

The editorial has a dynamic programming solution as provided by @only4, but I solved it with an alternate brute force approach.

Considering your example, let $A$ be "ozozizc" and $B$ be "zcozozi" and assume that we want to turn $A$ into $B$ using cyclic left shifts as instructed in the statement.
1. Concatenate $A$ to itself, to get $C$ as "ozozizcozozizc".
2. Locate $B$ in $C$. So $C$ would contain $B$ in the highlighted part: "ozozi[zcozozi]zc".
3. The index where $B$ is found is equal to the number of shifts we require to change $A$ into $B$, which is 5 in this case.
You can verify that the above procedure is correct.

Now a string of length $m$ has exactly $m$ rotations that can be obtained by cyclic shifts. So the final string we turn all our given strings into must be one of these $m$ strings.
So we can simply generate all $m$ rotations of any of the $n$ strings given to us as a target string $T$, and for each $T$ we can try to convert all $n$ strings into it. If we are unable to convert a string into $T$ then it is impossible to solve the problem and we print $-1$. Otherwise we easily find the $T$ which required minimum number of steps and output it.

The total complexity depends on the complexity of locating $B$ in $C$ in the procedure described above. If a naive string matching algorithm is used the total complexity is $\mathcal{O}(|S|^3 \times n)$. A linear string matching algorithm reduces it to $\mathcal{O}(|S|^2 \times n)$.
You can refer to my code here for better understanding. Hope this helps!

link

answered 22 Apr '17, 16:29

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×672
×349

question asked: 22 Apr '17, 10:34

question was seen: 654 times

last updated: 22 Apr '17, 16:40