Problem - B - Codeforces … 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.
- 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 \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