Algorithms · Lesson 8

Periods and Powers

Practice this topic →

Periods

A positive integer $p\le n$ is a period of a nonempty word $w=w[1..n]$ if

The word abababa has period 2 (positions 2 apart always agree) even though its length is 7 — a period need not divide the length.

Periods and borders

There is a direct bridge to the border theory from the Borders lesson.

If $w\left[i\right]=w[i+p]$ for all $i$, then $w[1..n-p]=w[p+1..n]$ — a border of length $n-p$. Conversely, a border of that length shifts the word onto itself by $p$ positions, giving the period.

The least period

Since the longest border of $w$ has length $f_w\left(n\right)$, the lemma gives the least period directly:

This is computed in linear time by the prefix function. In the visualization above, the border chain shows the successive border lengths; the longest border gives the least period.

Powers and the primitive root

For example 001001 = (001)² is a power with primitive root 001, while abababa is primitive.

So to test whether $w$ is a power: compute the prefix function, follow the border chain $b=f_w\left(n\right), f_w\left(b\right),\dots$, and check whether any $p=n-b$ divides $n$. The first such period gives the primitive root — and the whole test runs in linear time.

Practice

Find the least period

Find the primitive root

Practice this topic →Every quiz from this lesson, at four difficulties.