×

# MIKE AND STRINGS

 1 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 24●1●3 accept rate: 20% 1 You can find the editorials here http://codeforces.com/blog/entry/51652 (22 Apr '17, 12:28) only44★

 4 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! answered 22 Apr '17, 16:29 6★meooow ♦ 7.1k●7●18 accept rate: 48%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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