 # 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

1 Like

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!

6 Likes

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

1 Like