Доказательство для минимального числа проблемы вращения строки

Question

Допустим, мы вращаем строку по одной за раз («abcd» -> «bcda»). После нескольких вращений мы получим одну и ту же строку. Пусть t будет минимальным таким количеством вращений.

Например:

1. Для S = "aaaa", t = 1
2. Для S = "abcab c ", t = 3
3. Для S =" abcdef ", t = 6

Теперь мой вопрос, может ли быть какая-либо строка, для которой выполняется это условие: t> len (S) / 2 и t

Answer 1

Давайте предположим, что вы можете вращать вашу строку t раз, и она будет той же самой строкой. Затем, если вы повернете его еще раз по len (S) -t, вы точно получите ту же строку. Если мы предположим, что t>len(S)/2, мы получим это len(S)-t<len(S)/2, поэтому минимальное вращение всегда <=len(S)/2