Compression and periodicity

Why this matters when you build with AI

Repeat logic is easy to get almost right. A generated program can say that the string abcabcabcab is the block abc repeated three times. That answer looks plausible and is wrong, because the length 11 is not a multiple of 3. The program prints a number, the sample you tried may not show the problem, and the bug only appears on strings that are one letter off a pattern.

The fix is the same for any string code: write a slow version that is obviously right, then compare the two on many small random inputs. This lesson gives you the fast tools for periods and repeats, and a brute force for each of them.

The idea: a string that repeats

A period of a string s of length n is a number p such that s[i] equals s[i + p] for every i where both positions exist. In plain words, slide a copy of the string p places to the right and the overlapping letters match.

Take abaababaab, which has length 10. Its first five letters are abaab, and its last five letters are also abaab. So 5 is a period. Every string has the period n, because no pair of positions exists for that shift. The number we care about is the smallest period.

A border is a prefix that is also a suffix, and it is shorter than the whole string. A period p and a border of length n - p describe the same fact: the string matches itself after a shift of p. So the smallest period is n minus the length of the longest border.

The prefix function gives the longest border of every prefix in one pass. The value pi[i] is the length of the longest proper border of the prefix that ends at position i. The prefix function lesson covers how it is built. Here we only need its output.

For the whole string, the smallest period is:

smallest period = n - pi[n - 1]

Here is the table for abaababaab:

The last row gives pi[9] = 5, so the smallest period is 10 - 5 = 5. The check is direct: letters 0 to 4 are abaab, and letters 5 to 9 are abaab.

Here is the C++17 program that prints the prefix function, the smallest period and the exponent. It is the file we compiled and ran for this lesson.

#include <bits/stdc++.h>
using namespace std;
 
// pi[i]: length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i].
vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}
 
// Smallest p >= 1 such that s[i] == s[i + p] for every i where both indexes exist.
// Needs a non-empty s.
int smallest_period(const string& s) {
    vector<int> pi = prefix_function(s);
    return (int)s.size() - pi.back();
}
 
// Largest k such that s = u^k for some non-empty string u.
int power_exponent(const string& s) {
    int n = s.size();
    int p = smallest_period(s);
    return n % p == 0 ? n / p : 1;
}
 
int main() {
    string s;
    cin >> s;
    vector<int> pi = prefix_function(s);
    cout << "pi";
    for (int v : pi) cout << ' ' << v;
    cout << "\n";
    cout << "period " << smallest_period(s) << "\n";
    cout << "exponent " << power_exponent(s) << "\n";
    return 0;
}

Compile and run it like this:

g++ -std=c++17 -O2 -Wall -Wextra -o periods periods.cpp
echo abaababaab | ./periods

The real output on this machine (g++ 15.2.0, Linux) is:

pi 0 0 1 1 2 3 2 3 4 5
period 5
exponent 2

The exponent is 2 because the string is abaab written twice.

Exponent: how many times a string is a power

A string is a power when it is one block u written k times in a row, which we write as u^k. The exponent is the largest such k. abab is (ab)^2, so its exponent is 2. abcab is not a repeat of any block, so its exponent is 1.

The rule is short. Let p be the smallest period of s.

• If p divides n, the exponent is n / p.
• Otherwise the exponent is 1.

Two runs of the program show both cases. abcabcabc has smallest period 3, and 3 divides 9, so the exponent is 3. abcabcabcab has smallest period 3, but 3 does not divide 11, so the exponent is 1.

echo abcabcabc | ./periods
echo abcabcabcab | ./periods

Real output:

pi 0 0 0 1 2 3 4 5 6
period 3
exponent 3
pi 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
period 3
exponent 1

The periodicity lemma

The periodicity lemma says this. Let p and q be periods of s. If p + q - gcd(p, q) is at most n, then gcd(p, q) is also a period. Here gcd is the greatest common divisor.

In plain words: if a string has two periods, and they are not too large for its length, the string also has the greatest common divisor of the two as a period.

Two small examples. The string aabaabaa has length 8. It has periods 3 and 6. Here gcd(3, 6) = 3 and 3 + 6 - 3 = 6, which is at most 8, so 3 is a period. That matches what we can see, because the letters repeat every 3 places.

Now take periods 3 and 5 for a string of length 8. Here 3 + 5 - 1 = 7, which is at most 8, so the lemma says 1 is a period. A period of 1 means all letters are equal. We checked this with brute force: over the 3^8 strings on the letters a, b, c, exactly 3 strings have both periods 3 and 5, and all 3 are a single repeated letter.

The lemma gives the exponent rule. Suppose s = u^k with k at least 2, and let m be the length of u. Then m is a period, and 2m is at most n. Let p be the smallest period, so p is at most m. Then p + m - gcd(p, m) is at most p + m, which is at most 2m, which is at most n. The lemma says gcd(p, m) is a period. It is at most p, and p is the smallest period, so the gcd equals p. That means p divides m, and m divides n, so p divides n.

So if the smallest period does not divide n, no repeat with k at least 2 exists. If it does divide n, the block of length p is the repeat. Any other block length m that gives a repeat is a multiple of p by the same argument, so it gives an exponent of at most n / p.

This is the classic form of the lemma. The original source is not cited here, so look up the original statement before you cite it.

We tested the lemma on every string of length 1 to 12 over the letters a and b, and every pair of periods with the lemma's condition. The checker found 17844 pairs and no counterexample. Write the same kind of check yourself in the exercise below.

Compressing with runs and with repeated blocks

Run-length encoding (RLE) writes each run of equal letters as the letter and the run length. It is simple and it is lossless, which means you can get the original string back. Here is a short Python program that prints the smallest period and the exponent for three strings, and the RLE of each. It needs no input.

Real output:

abaababaab 5 2 a1b1a2b1a1b1a2b1
abcabcabcab 3 1 a1b1c1a1b1c1a1b1c1a1b1
aaaabbbcca 9 1 a4b3c2a1
wrong exponent for abcabcabcab: 3

Read the RLE column for abaababaab. It is a1b1a2b1a1b1a2b1, which is longer than the input. RLE only shrinks a string that has long runs, such as aaaabbbcca, which becomes a4b3c2a1.

Repeated-block encoding is the idea behind the next task. A piece of text written as a block u and a count k takes |u| letters for the block plus the count. If the block is short and the count is large, this is cheaper than writing every copy.

Original task: the cheapest block encoding

You get a string s of lowercase letters with length n, where 1 <= n <= 2000. Cut s into consecutive non-empty pieces. Each piece is written in one of two ways.

• If a piece has length L, smallest period p, p < L, and p divides L, the piece is written as its block plus a count. It costs p + 2.
• Otherwise the piece is written as it is, and it costs L.

Print the least total cost over all ways to cut s.

The input is one line with s. The output is one number. Here are four inputs with their answers:

• abababcabababcx gives 10. The cut is abababcabababc plus x. The first piece has smallest period 7, and 7 divides 14, so it costs 7 + 2 = 9. The letter x costs 1.
• aaaaaa gives 3. One piece aaaaaa has block a, so it costs 1 + 2.
• aa gives 2. Written as a block, it costs 1 + 2 = 3, which is more than two single letters at cost 1 each. So the cut is a plus a.
• xyz gives 3, since no repeat helps.

The second and third examples show that the cost of a repeat is only worth paying when the block is short compared with the copies it saves.

The method

Let dp[j] be the least cost to write the first j letters of s. Set dp[0] = 0. For every j, dp[j] is the minimum over all starts i < j of dp[i] + cost(s[i..j)), where s[i..j) is the piece with letters i to j - 1.

Checking every start and every end and computing the smallest period of each piece from scratch would be too slow. The trick: for a fixed start i, run the prefix function once on the suffix s[i..]. The smallest period of the prefix of length L is then L - pi[L - 1], so every piece starting at i gets its period in one pass. Each start costs O(n), and there are n starts, so the total is O(n^2). At n = 2000 that is about 4 million inner steps.

Here is the C++17 program. It is the file we compiled and ran.

#include <bits/stdc++.h>
using namespace std;
 
// pi[i]: length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i].
vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}
 
// Cost of writing the piece t: a piece that is u repeated k >= 2 times costs |u| + 2,
// any other piece costs its own length.
long long piece_cost(int len, int period) {
    if (period < len && len % period == 0) return period + 2;
    return len;
}
 
int main() {
    string s;
    cin >> s;
    int n = s.size();
    const long long INF = LLONG_MAX / 4;
    vector<long long> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        // dp[i] is final here, because every transition goes from a smaller index.
        string t = s.substr(i);
        vector<int> pi = prefix_function(t);
        for (int len = 1; len <= (int)t.size(); len++) {
            // Smallest period of the prefix t[0..len) is len - pi[len - 1].
            int period = len - pi[len - 1];
            dp[i + len] = min(dp[i + len], dp[i] + piece_cost(len, period));
        }
    }
    cout << dp[n] << "\n";
    return 0;
}

Compile with g++ -std=c++17 -O2 -Wall -Wextra -o block_dp block_dp.cpp. Real outputs on the four inputs above:

abababcabababcx -> 10
aaaaaa -> 3
aa -> 2
xyz -> 3

We tested this program against a brute force on 3000 random strings of length 1 to 12 over one to three letters. The brute force tries every way to cut the string, which is 2^(n-1) cuts, and computes each piece's period by checking every shift. All 3000 answers agreed. The random strings come from a fixed seed, so your own run will use different strings.

The Python program above computes the periods, and it is fast enough for that. We did not write or time a Python version of the full dynamic program, so the lesson does not claim one is fast enough. Use C++ for n = 2000.

Complexity

Time is O(n^2). Memory is O(n): the dp array has n + 1 values, and each start uses one prefix array of length at most n.

Hands-on exercise

Do this on your own machine.

1. Save the C++ program from the periods section as periods.cpp, and compile it.
2. Write a brute force in the language you like. It must test every shift q from 1 to n and return the smallest one that works. Also write a brute exponent that tries every length L that divides n.
3. Generate 1000 random strings of length 1 to 14 over the letters a and b. For each, compare your brute force with the fast program. Print the first string that differs, if any.
4. Repeat step 3 with the block program, using the brute force that tries all cuts.

Ask an AI tool for the first solution, then test it with step 3. Use this prompt:

Write a C++17 function that takes a string s and returns the largest k such that s = u^k for some non-empty u. Use the prefix function. Use only the standard library. Explain in two sentences why the smallest period decides the answer. Then give three test strings where the answer is not 1 and one where it is 1.

A good answer uses the smallest period n - pi[n - 1] and checks that it divides n. It must return 3 for abcabcabc and 1 for abcabcabcab. If it returns 3 for the second string, the divisibility check is missing. Keep the failing string as a test case.

Common mistakes

Dividing without checking divisibility. A program that prints n / period gives the wrong answer when the period does not divide n. Running the wrong version we wrote on purpose gives:

wrong exponent for abcabcabcab: 3

The correct answer is 1, because 11 is not a multiple of 3.

Using the border instead of the period. The border is pi[n - 1], and the period is n - pi[n - 1]. For abcab, the program prints pi 0 0 0 1 2, so pi[4] = 2. Printing 2 as the period is wrong. The period is 5 - 2 = 3, and the program prints period 3.

Charging a repeat for a single copy. A piece that is one copy of its block has p = L, so it must cost L, not p + 2. The check period < len in piece_cost is what handles this. Remove it, and aa costs 3 instead of 2.

Empty input. pi.back() on an empty vector reads past the start of the data, which is undefined behaviour in C++. The task says n >= 1, but a generated test file may still contain an empty line. Check for an empty string before you call smallest_period.

A shift loop with the wrong bound. When checking shift q, the comparison is s[i] == s[i + q] for i + q < n. A loop that runs i < n reads past the end of the string. The result may be a wrong answer or a crash, depending on the compiler. We did not run this case, so treat it as a rule to check by reading the code.

Checklist

• Write the brute force before the fast code, and keep it in the same folder.
• Compute the smallest period as n - pi[n - 1].
• Before you use n / p, check n % p == 0.
• A piece with period equal to its length costs its own length.
• Test on strings over one and two letters. Small alphabets create many repeats, so they find bugs faster.
• Test the empty input and a one-letter input by hand.
• Print the cost of the best cut, and keep the cuts in a second test if you need them.

Summary

A period is a shift at which a string matches itself, and the smallest period is n - pi[n - 1], read from the prefix function. The exponent of a string is n / p when the smallest period p divides n, and 1 otherwise, and the periodicity lemma explains why this rule holds. Run-length encoding helps only on long runs, while repeated-block encoding is a cut problem: a dynamic program over prefixes, with one prefix function per start, solves it in O(n^2).

Practice problems

Problem 1. Find the smallest period and the exponent of aabaabaa without running code. Then check with the program.

Hint: Build the border table, or test shifts 1 to 8 one at a time.

Show the answer

The smallest period is 3, because a a b repeats: positions 0 and 3 are a, 1 and 4 are a, 2 and 5 are b, 3 and 6 are a, 4 and 7 are a. The length 8 is not a multiple of 3, so the exponent is 1. The program prints period 3 and exponent 1.

Problem 2. Give the exponent of abcabcabc and of abab.

Hint: Find the smallest period, then check whether it divides the length.

Show the answer

abcabcabc has period 3, which divides 9, so the exponent is 3. abab has period 2, which divides 4, so the exponent is 2. The program prints exponent 3 and exponent 2.

Problem 3. For a string s of length n, the number of distinct rotations is the number of different strings you get by moving a prefix of s to the end. Show that this count equals the smallest period p when p divides n, and equals n otherwise. Test the claim on abab, abc, aaaa and abcab.

Hint: Ask which shifts r leave the string unchanged, then ask when two rotations can be equal.

Show the answer

Rotating s by r places gives s back only when s is a power of a block of length p, the smallest period, and r is a multiple of p. If p does not divide n, only r = 0 works. So two rotations are equal exactly when their shifts differ by a multiple of p, which gives n / p distinct rotations when p divides n, and n otherwise. Brute force on the four strings gives: abab has 2 rotations (smallest period 2), abc has 3 (period 3), aaaa has 1 (period 1), and abcab has 5 (period 3, which does not divide 5). A random check of 5000 strings of length 1 to 12 over a and b found no mismatch with the rule.

Problem 4. Compute the cheapest block encoding cost for aaaaaa, aa, xyz and ababab.

Hint: Use the piece costs from this lesson. Remember that a single copy costs its length.

Show the answer

aaaaaa costs 3, since one piece with block a costs 1 + 2. aa costs 2, two single letters. xyz costs 3. ababab costs 4: one piece with block ab repeated 3 times costs 2 + 2. The program prints 3, 2, 3 and 4 for these four inputs, in the order given.

Problem 5. Show that every string of length 8 with periods 3 and 5 uses one letter only.

Hint: The periodicity lemma applies when p + q - gcd(p, q) is at most n.

Show the answer

With p = 3 and q = 5, the gcd is 1, and 3 + 5 - 1 = 7, which is at most 8. The lemma says 1 is a period, so all letters are equal. A brute force over the 3^8 strings on the letters a, b, c found 3 strings with both periods, and all 3 use a single letter.