Proof for minimum number of String Rotation Problem

Question

Let's say we are rotating a string one at a time ("abcd" -> "bcda"). After some t rotations we get the same string. Let t be the minimum such number of rotations.

For ex:

For S = "aaaa", t = 1
For S = "abcabc", t = 3
For S = "abcdef", t = 6

Now my question is, can there be any string for which this condition holds : t > len(S)/2 and t < len(S)? If not can you please explain why?

Do you want a full proof? Or just an educated guess? Have you attempted anything yet to prove it yourself? — Zabuzard
– Zabuzard, Commented May 2, 2020 at 21:11
@Zabuzard As I understood, you are trying to prove using a constructive approach. You start with a prefix-free string, let's say "ab". And then to get a string for which t < len(S), you basically have to construct "abab" for which t < len(S) holds, and it would be len(S)/2. What if we start with string that is not prefix free. For ex S = "ababa" t = 5. Can you please elaborate and explain your intuition? Will t always be divisor of len(S)? Also, what are minimum number of characters I need to add to get t < len(S)? — darpanm
– darpanm, Commented May 2, 2020 at 21:32
Observe that no matter what t is, if u repeat rotation by t it always ends up with the same string again. To increase the size of t you also have to decrease the amount of repeated rotations by t until you receive the original string (all characters back at original position). That is 3 for hellohellohello and 2 for hellohello. The next possible value is 1, but that already gives you hello with t = len(S). Hence, there is no t in between. — Zabuzard
– Zabuzard, Commented May 2, 2020 at 21:43

Roman Svistunov · Accepted Answer · 2020-05-02 21:12:44Z

1

Let's assume you can rotate your string t times and it will be the same string. Then if you rotate it another len(S)-t times you will definitely get the same string. If we assume that t>len(S)/2 we straightforwardly get that len(S)-t<len(S)/2, so minimal rotation is always <=len(S)/2

answered May 2, 2020 at 21:12

Roman Svistunov

1,0797 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Proof for minimum number of String Rotation Problem

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related