1806. The Shortest Shift That Leaves It Unchanged

A number p between 1 and n is a PERIOD of s when s[i] equals s[i+p] for every i with i + p < n. Print the smallest period.

abcabcabc -> 3 three whole copies of abc abcabca -> 3 the last copy is cut short, and 3 is still a period abcdef -> 6 nothing shorter works, so the answer is the length aaaa -> 1

The second example is the one to sit with. A period does NOT have to divide the length. abcabca has period 3 because every character equals the one three places later, and the string simply runs out in the middle of the third copy. Problem 1807 asks the stricter question, where whole copies are required.

p = n is always a period, because the condition is then empty, so an answer always exists.

## What most people try first

Test p = 1, 2, 3, ... and check each one directly. Checking p costs n - p comparisons, so the total is about n^2 / 2. At n = 200000 with no short period, that is about 2 * 10^10 comparisons. The method below is one subtraction after an O(n) table, about 4 * 10^5 steps.

## Periods and borders are the same fact

smallest period = n - pi[n-1]

## Why that is true

Suppose p is a period. Then s[i] = s[i+p] for all valid i, which says the first n - p characters equal the last n - p characters. That is exactly the statement that s has a border of length n - p.

The converse runs the same way backwards: a border of length b means s[i] = s[i + (n-b)] for every valid i, so n - b is a period.

So periods and borders are in one-to-one correspondence through p = n - b, and the SMALLEST period corresponds to the LONGEST border, which problem 1804 already showed is pi[n-1].

Note that this correspondence needs borders whose two copies may overlap. For aaaa the longest border is aaa, which overlaps itself heavily, and the period it gives is 1.

## Cost

O(n) time and O(n) memory for the table, then one subtraction.

Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - the period does not have to divide the length