xiii. Runs and Periodicity

A run is a maximal substring $s[l,r)$ with smallest period $t$ and $r-l\ge 2t$. Runs theorem (Bannai et al. 2015): fewer than $n$ runs, and the sum of exponents $\frac{r-l}{t}$ is below $3n$. Every square (tandem repeat) $s[i,i+2k)$ lies in a unique run whose period divides $k$, so squares, cubes, “is there a repetition of exponent $\ge e$”, counting square occurrences and distinct squares reduce to the runs. Main–Lorentz divide and conquer finds all runs in $O(n\log n)$ ($n=2\cdot 10^5$ in about 0.2 s); the linear algorithm uses Lyndon roots and LCE queries (Lyndon Words).

Task	From the runs
all runs / maximal repetitions	runs(s)
occurrences of squares $ww$	${\sum }_{\text{runs}}{\sum }_{k=t,2t,\dots ,2k\le L}(L-2k+1)$
repetition of exponent $\ge e$ exists	some run has $L/t\ge e$
cubes, $k$-th powers	runs with $L\ge 3t$ / $L\ge kt$
primitively rooted squares, distinct squares	Lyndon roots of the runs (at most $n$ distinct squares)

template <class T> vector<int> zFunctionT(const T& s) {
    int n = sz(s); vector<int> z(n); if (n > 0) z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) { if (i < r) z[i] = min(r - i, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] > r) l = i, r = i + z[i]; }
    return z;
}
template <class T> vector<int> zMatch(const T& text, const T& pat) {   // e[i] = LCP(text[i..], pat)
    int n = sz(text), m = sz(pat); vector<int> z = zFunctionT(pat), e(n);
    for (int i = 0, l = 0, r = 0; i < n; i++) {
        int k = i < r ? min(r - i, z[i - l]) : 0;
        while (i + k < n && k < m && text[i + k] == pat[k]) k++;
        e[i] = k; if (i + k > r) l = i, r = i + k;
    }
    return e;
}
template <class T> vector<array<int, 3>> runs(const T& s) { // {t, l, r}: all runs, sorted
    int n = sz(s); vector<array<int, 3>> found;             // {l, r, p}: maximal p-periodic intervals with r - l >= 2p
    auto add = [&](int l, int r, int p) { if ((l == 0 || s[l - 1] != s[l - 1 + p]) && (r == n || s[r] != s[r - p])) found.push_back({l, r, p}); };
    auto crossing = [&](int lo, int mid, int hi) {           // p-periodic intervals containing s[mid - 1, mid + 1)
        T u(s.begin() + lo, s.begin() + mid), v(s.begin() + mid, s.begin() + hi), w(s.begin() + lo, s.begin() + hi), ru(u.rbegin(), u.rend()), rw(w.rbegin(), w.rend());
        int nu = sz(u), nv = sz(v);
        vector<int> zu = zFunctionT(ru), zv = zFunctionT(v), right = zMatch(w, v), left = zMatch(rw, ru);
        for (int p = 1; p <= nu; p++) {                      // contains s[mid - p, mid]
            int a = p < nu ? zu[p] : 0, b = right[nu - p];
            if (b > 0 && a + b >= p) add(mid - p - a, mid + b, p);
        }
        for (int p = 1; p <= nv; p++) {                      // contains s[mid - 1, mid + p)
            int c = p < nv ? zv[p] : 0, d = left[nv - p];
            if (d > 0 && c + d >= p) add(mid - d, mid + p + c, p);
        }
    };
    auto rec = [&](auto&& self, int lo, int hi) -> void { if (hi - lo < 2) return; int mid = (lo + hi) / 2; self(self, lo, mid); self(self, mid, hi); crossing(lo, mid, hi); };
    rec(rec, 0, n);
    sort(all(found)); vector<array<int, 3>> res;
    for (int i = 0; i < sz(found); i++) { auto [l, r, p] = found[i]; if (!(i > 0 && found[i - 1][0] == l && found[i - 1][1] == r)) res.push_back({p, l, r}); }   // keep the smallest period
    sort(all(res)); return res;
}
template <class T> ll countSquareOccurrences(const T& s) {
    ll total = 0;
    for (auto [t, l, r] : runs(s)) { int L = r - l; for (ll k = t; 2 * k <= L; k += t) total += L - 2 * k + 1; }
    return total;
}

Proof: Main–Lorentz and the square counting

Crossing intervals. Every run of length $\ge 2$ contains some split point mid of the recursion with $s[\mathrm{mid}-1],s[\mathrm{mid}]$ both inside, at the top-most level where it is cut. For a $p$-periodic interval containing $s[\mathrm{mid}-p..\mathrm{mid}]$ (left case), periodicity across mid means $s[x]=s[x+p]$ around mid: its extent to the right is $b=\mathrm{LCP}(s[\mathrm{mid}-p..),s[\mathrm{mid}..))$ (computed by right) and to the left $a$ = longest common suffix of $s[..\mathrm{mid}-p)$ and $s[..\mathrm{mid})$ (from the Z-function of the reversed left half); the interval $[\mathrm{mid}-p-a,\mathrm{mid}+b)$ is $p$-periodic and has length $\ge 2p$ iff $a+b\ge p$. The right case is symmetric. Restricting to $[lo,hi)$ can truncate a run; add keeps only intervals that are maximal in the whole string, and the same run found via several periods (multiples of the smallest) is deduplicated keeping the smallest $p$ (sorted order). Each level costs $O(n)$ Z-computations: $O(n\log n)$.

Squares. A square $ww$ with $|w|=k$ has period $k$; its smallest period $t$ satisfies $t+k\le 2k$, so by Fine–Wilf $\gcd (t,k)$ is a period and minimality gives $t\mid k$. Extending the $t$-periodic interval maximally gives a unique run with period $t$ containing it. Conversely, inside a run of length $L$ and period $t$, every window of length $2k$ with $t\mid k$ is a square. So each square occurrence is counted exactly once. Verified against brute-force enumeration of maximal periodic intervals and squares.

Related notes

• String Basics (Fine–Wilf, border–period duality)
• Lyndon Words (Lyndon roots, linear runs algorithm)
• Suffix Array (LCE queries)