Smallest Period — Solution & Editorial

Back to the Problem

Compute the KMP prefix function; the candidate period is |S| − π[|S|−1], and it is the true period iff it divides |S|.

Complexity: O(|S|)

Watch out: |S| − π[last] is only the period when it divides the length — abcab has period 5, not 3.