Why this matters when you build with AI
Counting distinct substrings sounds like a puzzle, but it is a measure of how repetitive a text is. A data team may want the number of distinct word groups (n-grams) in a training corpus, or the amount of copied text in a model's answer. A tool that counts every substring by position overstates these numbers, and a tool that stores every substring as text runs out of memory on large inputs. Both mistakes are common in code written with AI help.
When you check AI-written code for this problem, run it on ababa first. The correct answer is 9. A wrong formula often prints 15, which is the number of substrings counted by position, not by content. Then compare the code with a brute force program on short random strings. The code in this lesson was checked that way, and the checks are described below.
The idea: count each substring once
A substring is a block of consecutive characters, and it must not be empty. The string ababa has 15 substrings if you count by position: 5 of length 1, 4 of length 2, and so on. Many of them are equal. The letter a appears at positions 0, 2 and 4, so it is one distinct substring, not three. The 9 distinct substrings of ababa are a, b, ab, ba, aba, bab, abab, baba and ababa.
Every substring is a prefix of some suffix. A suffix is the tail of the string starting at one position, so the suffixes of ababa are ababa, baba, aba, ba and a. The prefixes of ababa are a, ab, aba, abab and ababa, which are five distinct substrings. So the count of distinct substrings is the number of prefixes of all suffixes, with repeats removed.
The trick is to sort the suffixes. Sorted suffixes that start with the same letters are next to each other. When you walk the sorted list, a suffix shares some prefixes with the one before it, and those prefixes were already counted. The shared length is the longest common prefix (LCP) of the two neighbours. A suffix with length len and shared length h adds len - h new distinct substrings. The total is the sum of len over all suffixes, minus the sum of the neighbour LCPs. The sum of len is n(n+1)/2, so for ababa the count is 15 - 6 = 9.
The three methods below give that answer in different ways.
Method 1: suffix array with LCP
The suffix array (lesson 05) lists the start positions of the sorted suffixes. Kasai's algorithm (also in lesson 05) finds the neighbour LCPs in linear time. The table for ababa is printed by the code below:
row sa suffix lcp_with_previous
0 4 a 0
1 2 aba 1
2 0 ababa 3
3 3 ba 0
4 1 baba 2The LCP values add to 6. The formula gives 15 - 6 = 9. The code here builds the suffix array with a simple sort in each round, so it runs in O(n log^2 n). The radix sort version in lesson 05 runs in O(n log n).
Method 2: suffix automaton
A suffix automaton is a small state machine that accepts exactly the substrings of a string (lesson 06 explains how it is built). Each state groups the substrings that end at the same set of positions. A state v holds the substrings with lengths from len[link[v]] + 1 up to len[v], where link[v] is the suffix link, which points to the state of the next shorter group. So a state adds len[v] - len[link[v]] distinct substrings, and the total is the sum over all states except the start state.
The code repeats the construction so that the file compiles on its own. It has at most 2n states, so the memory is linear in n for a fixed alphabet.
Method 3: hashing every substring
The simplest method hashes every substring and counts the distinct hashes. A rolling hash (lesson 03) gives the hash of any substring in constant time after a linear precomputation. There are n(n+1)/2 substrings, so this method is O(n^2) in time and memory. It is only for small n.
The hash must not be a plain 64-bit overflow hash. Multiplying by a base modulo 2^64 lets a crafted word collide with its complement. The Thue-Morse word of length 2^k is built from the parity of the number of 1 bits in each position. The next program checks the claim with a real run:
#include <bits/stdc++.h>
using namespace std;
// Hash of s with natural unsigned 64-bit overflow: h = sum s[i] * B^(n-1-i) mod 2^64.
unsigned long long hash64(const string& s, unsigned long long B) {
unsigned long long h = 0;
for (char c : s) h = h * B + (unsigned long long)(c - 'a' + 1);
return h;
}
// Thue-Morse word of length 2^k over 'a'/'b': t[i] = parity of popcount(i).
string thue_morse(int k) {
string t;
for (int i = 0; i < (1 << k); i++) t.push_back(__builtin_popcount(i) % 2 ? 'b' : 'a');
return t;
}
string complement(string s) { for (char& c : s) c = c == 'a' ? 'b' : 'a'; return s; }
int main() {
mt19937_64 rng(99);
for (int k : {9, 10, 11}) {
string t = thue_morse(k), u = complement(t);
int trials = 5, collide = 0;
for (int tr = 0; tr < trials; tr++) {
unsigned long long B = rng() | 1ULL; // random odd base
if (hash64(t, B) == hash64(u, B)) collide++;
}
cout << "k=" << k << " length=" << t.size() << " odd bases tried=" << trials
<< " collisions=" << collide << "\n";
}
string t = thue_morse(11), u = complement(t);
cout << "k=11 with base 131: " << (hash64(t, 131) == hash64(u, 131) ? "collide" : "differ") << "\n";
cout << "k=11 with base 1000003: " << (hash64(t, 1000003) == hash64(u, 1000003) ? "collide" : "differ") << "\n";
return 0;
}Its output on this machine:
k=9 length=512 odd bases tried=5 collisions=1
k=10 length=1024 odd bases tried=5 collisions=5
k=11 length=2048 odd bases tried=5 collisions=5
k=11 with base 131: collide
k=11 with base 1000003: collideThe result depends on the base and the length. With 5 random odd bases, the length-512 word collided once, and the length-1024 and length-2048 words collided in every trial. The hash code in the reference program uses the prime 2^61 - 1 with a fixed base, and the same Thue-Morse words are not part of its tests. Use a modulus, a random base, and store the length beside the hash.
Standard technique: the reference program
The program below holds all three methods, the offline range method from the next section, a brute force checker, and a demo on ababa. It compiles with g++ -O2 -std=c++17 -Wall -Wextra with no warnings.
#include <bits/stdc++.h>
using namespace std;
// ---------- Method 1: suffix array (prefix doubling) + Kasai LCP ----------
// Simple version: sorts with std::sort each round, O(n log^2 n). Lesson 05 has the radix version.
vector<int> suffix_array(const string& s) {
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) { sa[i] = i; rk[i] = s[i]; }
for (int k = 1;; k <<= 1) {
auto key = [&](int i) { return make_pair(rk[i], i + k < n ? rk[i + k] : -1); };
sort(sa.begin(), sa.end(), [&](int x, int y) { return key(x) < key(y); });
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]));
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break;
}
return sa;
}
// lcp[i] = LCP of suffixes sa[i-1] and sa[i]; lcp[0] = 0.
vector<int> kasai(const string& s, const vector<int>& sa) {
int n = s.size();
vector<int> rank(n), lcp(n, 0);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0) { h = 0; continue; }
int j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rank[i]] = h;
if (h > 0) h--;
}
return lcp;
}
long long distinct_sa(const string& s) {
int n = s.size();
if (n == 0) return 0;
auto sa = suffix_array(s);
auto lcp = kasai(s, sa);
long long total = (long long)n * (n + 1) / 2; // all suffixes, counted with repeats
for (int i = 1; i < n; i++) total -= lcp[i]; // repeated prefixes are counted once
return total;
}
// ---------- Method 2: suffix automaton ----------
struct SuffixAutomaton {
struct State { int len, link; int next[26]; };
vector<State> st;
int last = 0;
static State make_state(int len, int link) {
State s;
s.len = len; s.link = link;
fill(begin(s.next), end(s.next), -1);
return s;
}
explicit SuffixAutomaton(size_t n) {
st.reserve(2 * n + 2);
st.push_back(make_state(0, -1));
}
void extend(int c) {
int cur = st.size();
st.push_back(make_state(st[last].len + 1, -1));
int p = last;
while (p != -1 && st[p].next[c] == -1) { st[p].next[c] = cur; p = st[p].link; }
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) {
st[cur].link = q;
} else {
int clone = st.size();
State copy = st[q];
copy.len = st[p].len + 1;
st.push_back(copy);
while (p != -1 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; }
st[q].link = clone;
st[cur].link = clone;
}
}
last = cur;
}
};
long long distinct_sam(const string& s) {
SuffixAutomaton sam(s.size());
for (char ch : s) sam.extend(ch - 'a');
long long total = 0;
for (size_t v = 1; v < sam.st.size(); v++)
total += sam.st[v].len - sam.st[sam.st[v].link].len; // strings that end in state v
return total;
}
// ---------- Method 3: hashing every substring, O(n^2) substrings ----------
const unsigned long long MOD = (1ULL << 61) - 1;
unsigned long long mulmod(unsigned long long a, unsigned long long b) {
__uint128_t c = (__uint128_t)a * b;
unsigned long long r = (unsigned long long)(c & MOD) + (unsigned long long)(c >> 61);
if (r >= MOD) r -= MOD;
if (r >= MOD) r -= MOD;
return r;
}
long long distinct_hash(const string& s, unsigned long long base) {
int n = s.size();
vector<unsigned long long> h(n + 1, 0), pw(n + 1, 1);
for (int i = 0; i < n; i++) {
h[i + 1] = (mulmod(h[i], base) + (unsigned long long)(s[i] - 'a' + 1)) % MOD;
pw[i + 1] = mulmod(pw[i], base);
}
vector<pair<unsigned long long, int>> all;
all.reserve((size_t)n * (n + 1) / 2);
for (int i = 0; i < n; i++)
for (int len = 1; i + len <= n; len++) {
unsigned long long v = (h[i + len] + MOD - mulmod(h[i], pw[len])) % MOD;
all.push_back({v, len});
}
sort(all.begin(), all.end());
return unique(all.begin(), all.end()) - all.begin();
}
// ---------- Offline range queries: distinct substrings of s[l..r] ----------
// For each r, the substring counted at its rightmost occurrence inside [0..r] is (i, L).
// Start i contributes w = (r - i + 1) - Q(i, r), where Q(i, r) = max over j in (i, r]
// of min(LCP(i, j), r - j + 1). Answer for [l, r] = sum of w over i in [l, r].
vector<long long> distinct_in_ranges(const string& s, const vector<pair<int, int>>& qs) {
int n = s.size();
vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
for (int i = n - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
if (s[i] == s[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
vector<vector<int>> byR(n);
for (int q = 0; q < (int)qs.size(); q++) byR[qs[q].second].push_back(q);
vector<long long> ans(qs.size(), 0);
vector<long long> w(n, 0);
for (int r = 0; r < n; r++) {
for (int i = 0; i <= r; i++) {
int Q = 0;
for (int j = i + 1; j <= r; j++) Q = max(Q, min(lcp[i][j], r - j + 1));
w[i] = (r - i + 1) - Q;
}
for (int q : byR[r]) {
long long sum = 0;
for (int i = qs[q].first; i <= r; i++) sum += w[i];
ans[q] = sum;
}
}
return ans;
}
long long brute_distinct(const string& s) {
set<string> seen;
for (size_t i = 0; i < s.size(); i++)
for (size_t len = 1; i + len <= s.size(); len++) seen.insert(s.substr(i, len));
return seen.size();
}
int main() {
string s = "ababa";
auto sa = suffix_array(s);
auto lcp = kasai(s, sa);
cout << "s = " << s << "\n";
cout << "row sa suffix lcp_with_previous\n";
for (int i = 0; i < (int)s.size(); i++)
cout << i << " " << sa[i] << " " << s.substr(sa[i]) << " " << lcp[i] << "\n";
cout << "suffix array + LCP: " << distinct_sa(s) << "\n";
cout << "suffix automaton: " << distinct_sam(s) << "\n";
cout << "hashing: " << distinct_hash(s, 131) << "\n";
cout << "brute force: " << brute_distinct(s) << "\n";
vector<pair<int, int>> qs = {{0, 4}, {1, 3}, {2, 2}, {3, 4}};
auto ans = distinct_in_ranges(s, qs);
for (size_t q = 0; q < qs.size(); q++) {
string piece = s.substr(qs[q].first, qs[q].second - qs[q].first + 1);
cout << "s[" << qs[q].first << ".." << qs[q].second << "] = " << piece
<< ": " << ans[q] << " (brute force " << brute_distinct(piece) << ")\n";
}
return 0;
}Its output:
s = ababa
row sa suffix lcp_with_previous
0 4 a 0
1 2 aba 1
2 0 ababa 3
3 3 ba 0
4 1 baba 2
suffix array + LCP: 9
suffix automaton: 9
hashing: 9
brute force: 9
s[0..4] = ababa: 9 (brute force 9)
s[1..3] = bab: 5 (brute force 5)
s[2..2] = a: 1 (brute force 1)
s[3..4] = ba: 3 (brute force 3)The three methods agree with the brute force, which builds a set of strings. I checked the same code with a separate test program. It compared the three methods with the brute force on 4000 random strings of length 0 to 39, over alphabets of one, two, three and 26 letters, and it compared the range method on 600 batches of 30 random ranges each. All 4600 checks passed.
Here is the same idea in Python, short enough to read. It is only for small strings, because it sorts the suffixes as text:
Its output:
ababa 9 9
aaaa 4 4
abcd 10 10Offline version: distinct substrings in a range
A query asks for the number of distinct substrings of s[l..r], the part of the string from position l to r inclusive. If there are many queries, it helps to answer them in one pass with the queries sorted by r.
Here is the key fact. Each distinct substring of s[0..r] has a last occurrence, the start position where it occurs for the final time before r. Count each distinct substring once, at its last occurrence. A substring that occurs in s[l..r] has an occurrence inside [l..r], so its last occurrence inside [0..r] starts at a position i >= l. A substring whose last occurrence is before l does not occur in s[l..r]. So the answer for [l, r] is the number of pairs (i, L) with l <= i, i + L - 1 <= r, and no later copy of the same string inside [0..r].
Fix r. For a start i, the length L is a last occurrence exactly when no later start j in (i, r] has a copy of length L that fits before r. A copy at j of length L exists exactly when L <= LCP(i, j) and L <= r - j + 1. So define
Q(i, r) = max over j in (i, r] of min(LCP(i, j), r - j + 1)
Then the valid lengths are those with L > Q(i, r), up to r - i + 1. There are (r - i + 1) - Q(i, r) of them. Call that w(i). It does not depend on l, so the answer for [l, r] is the sum of w(i) for i from l to r.
The code computes the LCP table once, then for each r it computes all w(i) and answers the queries with that r. The time is O(n^3) in the simple form, with an O(n^2) LCP table. I did not find or verify a faster method, so this lesson does not claim one.
Worked original problem: distinct words in a window
Statement. You get a lowercase string s of length n, with n at most 300, and q queries, with q at most 1000. Each query gives l and r, with 0 <= l <= r < n. For each query, print the number of distinct nonempty substrings of s[l..r].
Input. The first line has s. The second line has q. Each of the next q lines has l and r.
Output. One number per query, in input order.
Example. For s = ababa and the queries (0,4), (1,3), (2,2) and (3,4), the answers are 9, 5, 1 and 3. The program prints these values, and the brute force column agrees.
Solution. The function distinct_in_ranges is the solution. The output above is the real output of the program on that input. Check the answer by hand for (1,3): the substring is bab, and its distinct substrings are b, a, ba, ab and bab, which is 5.
Limits and timing. With n = 300 and q = 1000, the program ran in 5 ms on this machine. The timing depends on the machine, so treat it as one measurement.
Complexity
| Method | Time | Memory | Notes |
|---|---|---|---|
| Suffix array with LCP (this code) | O(n log^2 n) | O(n) | Lesson 05 gives O(n log n) |
| Suffix automaton | O(n) | O(n) states | Lesson 06 covers the construction |
| Hashing every substring | O(n^2 log n) | O(n^2) | Only for small n |
| Offline range method | O(n^2) LCP table and O(n^3) naive queries | O(n^2) | Measured 5 ms for n = 300 and 1000 queries |
Measured on this machine with random binary strings of length 200000: the suffix array with LCP took 287 ms and the suffix automaton took 409 ms. For length 20000 the times were 14 ms and 3 ms. The two methods gave the same answer, 19996798313 for the long string. The hashing method took 415 ms for length 2000. Hashing every substring at length 200000 would store about 2.0 times 10^10 entries, which is about 320 GB at 16 bytes each. That is arithmetic, not a measurement.
Common mistakes
Counting by position. Summing len over all suffixes gives n(n+1)/2. For ababa the output of this formula is 15, not 9. The missing step is subtracting the neighbour LCPs. A quick brute force on short strings catches this.
Forgetting the subtraction in the automaton. The count for a state is len[v] - len[link[v]], not len[v]. Summing len counts too much, because the shorter strings of a state also belong to the states that link points to, and they are counted there. Test the formula on ababa and aaaa, which should give 9 and 4.
Hashing without length. Two different substrings of different lengths can share a hash value. The hashing code stores the pair of hash and length, so a collision between lengths is ruled out. Without the length, a collision would merge two different substrings and the count would drop by one.
A plain 64-bit overflow hash. The Thue-Morse output above shows the failure. Use the prime modulus 2^61 - 1 with a random base, as lesson 03 describes.
Inclusive and exclusive ends. The range method uses inclusive r. If you pass an exclusive end, the answer is for the wrong substring. The demo prints the substring next to its count so you can check which one was counted.
Forgetting to group queries by r. The offline method computes the w values for one r at a time. A query answered with the wrong r gets the wrong sum.
Checklist
- Test every method on
ababa(9) andaaaa(4) before any larger test. - Compare the methods with a brute force program on short random strings, and include the empty string.
- Remember the LCP subtraction, or the
len[link[v]]subtraction, in the formula. - Store the length with every hash, and use a modulus with a random base.
- Use the suffix array or the suffix automaton for large
n, not the hashing method. - For range queries, check
landrare inclusive, and group the queries byr.
Practice problems
Practice 1: a string with repeats
Count the distinct substrings of aabaa.
Hint: write the suffixes in sorted order, then count the new prefixes of each one.
Show the answer
- The suffix array, the suffix automaton and the brute force all print 11 for
aabaa.
Practice 2: all one letter
Show that a string of n copies of one letter has exactly n distinct substrings, and check it for n = 6.
Hint: each length gives one substring.
Show the answer
Each length from 1 to n gives exactly one distinct substring, the run of that many copies. So the answer is n. For aaaaaa the program gives 6.
Practice 3: one range
For s = ababa, find the number of distinct substrings of s[1..2].
Hint: the substring is two letters long, so list its pieces.
Show the answer
The substring is ba. Its distinct substrings are b, a and ba, so the answer is 3. The range method prints 3 for this query.
Practice 4: memory for hashing
Estimate the memory for the hashing method on a string of length 200000, storing one pair of hash and length per substring at 16 bytes each.
Hint: the number of substrings is n(n+1)/2.
Show the answer
200000 * 200001 / 2 = 20000100000, about 2.0 times 10^10 entries. At 16 bytes each that is about 320 GB. For the same string the suffix array needs a few megabytes, and the automaton with 26 links per state needs tens of megabytes.
Summary
Each distinct substring is a prefix of some suffix, and sorting the suffixes lets you count each one once. The suffix array with LCP and the suffix automaton both give the count in near-linear time. Hashing every substring is simple and correct for small inputs, but its memory grows with the square of the length, and a plain 64-bit overflow hash can be attacked. The range method counts each substring at its last occurrence, which makes the answer for a range a sum over starts.