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

# MIKE AND STRINGS

**meooow**#2

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.

- Concatenate A to itself, to get C as
**“ozozizcozozizc”**. - Locate B in C. So C would contain B in the highlighted part:
**“ozozi[zcozozi]zc”**. - 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 imes n). A linear string matching algorithm reduces it to \mathcal{O}(|S|^2 imes n).

You can refer to my code here for better understanding. Hope this helps!