1847. How Many Rotations Change Nothing
Rotating s by k places means taking s[k..] followed by s[..k]. Count the
values of k from 0 to n-1 for which the rotation is s itself. Rotating by 0
always is, so the answer is at least 1.
abcabcabc -> 3 k = 0, 3, 6
aaaa -> 4 every rotation
abcdef -> 1 only k = 0
abcabca -> 1 period 3, but 3 does not divide 7
aabaabaabaab -> 4
abcabca is the case that separates period from rotation. Its smallest period
is 3, and yet rotating by 3 gives abcaabc, which is different, because the
string is not a whole number of copies.
## What most people try first
Build each of the n rotations and compare with s. That is O(n^2):
4 * 10^10 character operations at n = 200000. The method below is
O(n), about 4 * 10^5.
## Count the copies
p = n - pi[n-1] the smallest period, from problem 1806
if n mod p == 0: answer n / p
else: answer 1
## Why the answer is the number of copies
Rotating by k leaves s unchanged exactly when k is a period of s that
divides n. One direction: if s[k..] + s[..k] equals s, then s[i] equals
s[(i+k) mod n] for every i, which is the period condition read around the
circle, and it forces the string to be n / gcd(n, k) copies of a block. The
other direction: if s is a block of length p repeated c times, then
rotating by any multiple of p maps each copy onto another and leaves the
string identical.
So the fixed rotations are exactly the multiples of the smallest DIVIDING
period, of which there are n / p in the range 0 to n-1.
When p does not divide n, no divisor-period exists below n by the argument
in problem 1807, so only k = 0 works.
## The mistake the tests catch
Answering n / p without the divisibility test. On ababa the smallest period
is 2 and the length is 5, so that version prints 2 where the answer is 1; on
abcabca it prints 2 as well. Both were confirmed by running it. Integer
division hides the error rather than revealing it.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - rotating by 0 counts, so the answer is never 0 - a rotation is not an occurrence, so overlap does not arise, and a count of shift amounts is wanted
Input
A single line containing the string s, of lowercase English letters.
Output
Print one integer on its own line: how many values of k from 0 to n-1 leave the string unchanged when the first k characters are moved to the back. The answer is at least 1, since k = 0 always works.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.