Suffix trie for substring queries

Why this matters

A substring is a run of letters taken from inside a longer text. The word nan is a substring of banana, because the letters n, a, n appear next to each other in that order. A text editor's Find box, a search over a log file and a check for a bad word in a message all ask this question: does this short pattern appear anywhere in this longer text?

The simple method checks every starting position. For a text of length n and a pattern of length m, that costs about n times m letter comparisons for each query. A suffix trie answers the same question by walking the pattern once through a tree, and the cost depends on the pattern's length and not on the text's length. The price is a large tree built in advance.

Earlier lessons in this module covered tries of words. A trie of word endings is the same tool with a different input. Before you start, you need two words from this lesson. A prefix is the start of a string, such as ban for banana. A suffix is the end of a string, such as ana for banana.

The key idea

Look at the suffixes of banana. Each suffix starts at a different letter and runs to the end of the word:

suffix starting at 0: banana
suffix starting at 1: anana
suffix starting at 2: nana
suffix starting at 3: ana
suffix starting at 4: na
suffix starting at 5: a

Every substring of banana is the start of one of these lines. The substring nan starts at position 2, so it is the start of the suffix nana. The substring ana starts at position 1 and also at position 3, so it is the start of both anana and ana. Any substring of the text starts at some position, and from that position it is a prefix of the suffix that begins there.

That gives the rule for this lesson. A pattern is a substring of the text exactly when it is a prefix of at least one suffix of the text. If you put every suffix into one trie, asking whether a pattern is a substring becomes the same question as asking whether the trie contains a path that spells the pattern. The trie lesson already showed that question, so the walk is the one you already know.

Building the trie for banana

Start with an empty trie that has only a root. Insert the six suffixes one at a time. Each insert walks from the root, creates the missing nodes and moves on.

1. Insert banana. It creates the path b, a, n, a, n, a.
2. Insert anana. The root has no a child, so it creates a new path a, n, a, n, a. This path shares nothing with the first one, because the first letter differs from b.
3. Insert nana. A new path n, a, n, a starts at the root.
4. Insert ana. The path a, n, a already exists from step 2, so the insert adds nothing new.
5. Insert na. The path n, a already exists from step 3, so nothing new is added.
6. Insert a. The node a already exists under the root, so nothing new is added.

Each node also counts how many suffixes pass through it. The count tells you how many times the pattern that leads to the node starts in the text. A pattern of ana leads to a node that the suffixes anana and ana both pass through, so the count is 2. This is the number of starting positions, and the two overlapping occurrences of ana are the two positions 1 and 3.

The code

The class below keeps a count in each node, called passes. The code uses an array of 26 slots per node, the same layout as the array trie in the previous lesson, so the letters must be lowercase. build inserts every suffix. contains and count walk the pattern. count returns the number of starting positions, and contains returns true when that number is at least one.

class SuffixTrie {
public:
    SuffixTrie() { nodes_.push_back(Node{}); }
 
    // Insert every suffix of text: text, text without its first letter, and so on.
    void build(string_view text) {
        for (size_t start = 0; start < text.size(); ++start) {
            insert_suffix(text.substr(start));
        }
    }
 
    bool contains(string_view pattern) const { return walk(pattern) != -1; }
 
    // Number of positions where pattern starts in the text, overlaps included.
    int count(string_view pattern) const {
        int node = walk(pattern);
        return node == -1 ? 0 : nodes_[node].passes;
    }
 
    size_t node_count() const { return nodes_.size(); }
    size_t bytes() const { return nodes_.size() * sizeof(Node); }
 
private:
    struct Node {
        array<int, 26> next;
        int passes = 0;  // how many suffixes start with the letters on the path to this node
        Node() { next.fill(-1); }
    };
    vector<Node> nodes_;
 
    void insert_suffix(string_view suffix) {
        int cur = 0;
        nodes_[cur].passes++;
        for (char c : suffix) {
            int slot = c - 'a';
            if (nodes_[cur].next[slot] == -1) {
                nodes_.push_back(Node{});
                nodes_[cur].next[slot] = static_cast<int>(nodes_.size()) - 1;
            }
            cur = nodes_[cur].next[slot];
            nodes_[cur].passes++;
        }
    }
 
    int walk(string_view pattern) const {
        if (pattern.empty()) return -1;
        int cur = 0;
        for (char c : pattern) {
            cur = nodes_[cur].next[c - 'a'];
            if (cur == -1) return -1;
        }
        return cur;
    }
};

walk returns the index of the node that spells the pattern, or -1 when the path breaks. It is the only place that follows links, so contains and count both use it. The empty pattern returns -1, so an empty string is never reported as a substring. That choice is a rule of this code, and a different program might count the empty string differently.

Here is the same class in a small program. The middle part checks the node-count rule against a slow method, which the next section explains.

size_t distinct_substrings(const string& text) {
    set<string> seen;
    for (size_t i = 0; i < text.size(); ++i)
        for (size_t len = 1; i + len <= text.size(); ++len)
            seen.insert(text.substr(i, len));
    return seen.size();
}
 
int main() {
    cout << boolalpha;
 
    SuffixTrie banana;
    banana.build("banana");
    cout << "nodes for banana: " << banana.node_count() << "\n";
    for (string_view p : {"nan", "nab", "ana", "a", "anana", "bananas"}) {
        cout << p << ": contains " << banana.contains(p) << ", count " << banana.count(p) << "\n";
    }
    cout << "\n";
 
    // Check the rule: nodes = 1 (root) + number of distinct substrings.
    uint32_t state = 7;
    auto next = [&state]() {
        state = state * 1664525u + 1013904223u;
        return state >> 8;
    };
    bool all_ok = true;
    for (int trial = 0; trial < 200; ++trial) {
        string text;
        size_t len = 1 + next() % 40;
        for (size_t k = 0; k < len; ++k) text.push_back(static_cast<char>('a' + next() % 3));
        SuffixTrie t;
        t.build(text);
        if (t.node_count() != 1 + distinct_substrings(text)) all_ok = false;
    }
    cout << "node rule holds for 200 random texts: " << all_ok << "\n\n";
 
    // Memory growth on random text over 26 letters.
    for (size_t n : {250, 500, 1000, 2000}) {
        string text;
        for (size_t k = 0; k < n; ++k) text.push_back(static_cast<char>('a' + next() % 26));
        SuffixTrie t;
        t.build(text);
        size_t nodes = t.node_count();
        cout << "text length " << n << ": nodes " << nodes
             << ", n*(n+1)/2 = " << n * (n + 1) / 2
             << ", bytes " << t.bytes() << "\n";
    }
}

The program uses set and string in the helper, so it needs <set> and <string> in addition to the headers the class uses, <array>, <cstdint>, <iostream>, <string_view> and <vector>. It also needs using namespace std;. This is the output of one run:

nodes for banana: 16
nan: contains true, count 1
nab: contains false, count 0
ana: contains true, count 2
a: contains true, count 3
anana: contains true, count 1
bananas: contains false, count 0
 
node rule holds for 200 random texts: true
 
text length 250: nodes 31115, n*(n+1)/2 = 31375, bytes 3360420
text length 500: nodes 124644, n*(n+1)/2 = 125250, bytes 13461552
text length 1000: nodes 499026, n*(n+1)/2 = 500500, bytes 53894808
text length 2000: nodes 1997549, n*(n+1)/2 = 2001000, bytes 215735292

Read the first block. nan is found once, at position 2. ana is found twice, at positions 1 and 3. a is found three times, at positions 1, 3 and 5. anana is found once, at position 1. bananas is not found, because the text has no letter s after the last a. nab is not found, because no suffix starts with nab.

The node count for banana is 16. The root has no letter, and the other 15 nodes are the 15 different substrings of banana. The check in the middle of the program tests this rule on 200 short random texts. The brute-force method stores each substring as a string in a set, and the trie's node count matches its size plus one for the root, for every text. The output says true.

Why the trie is large

The rule explains the memory cost. Each node in the trie stands for one distinct substring. A text of length n has at most n(n+1)/2 substrings, counting each start position and each length once. For a text with no repeats, almost every substring is distinct, so the trie has nearly n(n+1)/2 nodes.

The random-text rows show this. For a text of length 2000, the trie has 1,997,549 nodes, and the bound is 2,001,000. Each node costs 108 bytes in this array layout, so the 2000-letter text needs about 216 MB. The node count grows with the square of the text length, not with the length itself.

A text of length 10,000 would need about 50 million nodes. At 108 bytes each, that is about 5.4 GB for one structure. The trie is a good tool for short texts, a few thousand letters, or for texts with many repeats, which create fewer distinct substrings. It is a poor tool for a long document.

The build also takes time. Inserting each suffix walks its whole length, so the total number of letters walked is the sum of all suffix lengths, which is n(n+1)/2. A query, once the trie exists, walks only the pattern. A pattern of 5 letters costs 5 steps whether the text has 100 letters or 100,000.

A second example

Take the text mississippi, which has 11 letters and repeats the letters i, s and p many times. Its suffixes are mississippi, ississippi, ssissippi, sissippi, issippi, ssippi, sippi, ippi, ppi, pi and i. A pattern like issi is a prefix of two of them, ississippi and issippi. The count is 2, so issi occurs at positions 1 and 4.

Some counting goes wrong when you forget the overlaps. In aaaa the pattern aa starts at positions 0, 1 and 2. The three occurrences overlap, and a trie that stores each suffix once still counts all three, because the suffixes aaaa, aaa and aa each pass through the node for aa.

The next example shows the case where the pattern is not in the text at all, and the walk stops early. Searching bb in abab fails at the second letter. The root has an a child and a b child, the b child has no b child, so the walk stops with -1, and the answer is false.

The cost next to the simple search

The table below compares the two methods for one text of length n and one pattern of length m.

For one query on a short text, the simple search is faster, because it has no build step. For many queries on the same text, the trie pays for its build after enough of them. For a long text, the memory cost usually rules the trie out, and a suffix array or a suffix tree is the usual choice. A suffix array stores the starting positions of the sorted suffixes in an array of about n integers. A suffix tree is a trie of suffixes with long chains squashed into single edges, which is the same squashing idea as the radix tree lesson earlier in this module.

What the trie cannot tell you

The trie answers "does it occur" and "how many times". It does not answer "where". The counts in passes add up without remembering which starting positions they came from.

If you need the positions, each node has to store a list. Insert the suffix that starts at index i, and add i to the list of every node the suffix passes through. Then the list at the node for issi holds 1 and 4 for mississippi, which are the two starting positions from the example above. A query walks to the node and reads its list, so the answer comes out in time proportional to the pattern length plus the number of occurrences.

The price is memory. Each suffix of length L adds L entries to lists, one per node on its path. The total number of list entries is therefore the sum of all suffix lengths, which is n(n+1)/2 again, and it is stored on top of the nodes. A text that already needs gigabytes for its nodes needs more for its lists. This is why programs that need positions for a long text usually use a suffix array, which stores the starting positions in one array of n integers.

Common mistakes

Forgetting the include for uint32_t

The random number code in the demo uses uint32_t, which lives in <cstdint>. Leaving that include out gives this error with g++:

suffix_trie.cpp: In function ‘int main()’:
suffix_trie.cpp:84:5: error: ‘uint32_t’ was not declared in this scope
   84 |     uint32_t state = 7;
      |     ^~~~~~~~
suffix_trie.cpp:7:1: note: ‘uint32_t’ is defined in header ‘<cstdint>’; this is probably fixable by adding ‘#include <cstdint>’

The error message names the header to add. The lambda that uses state then fails too, with messages that state was not declared in this scope. Those lines disappear once the include is added. Read the first error and fix it before the others.

Making count or contains a non-const method

contains and count do not change the trie, so they are declared const. If a helper that they call is not const, the compiler refuses the call. This small example reproduces the error:

class Counter {
public:
    int total() const { return value_ + bump(); }
private:
    int value_ = 1;
    int bump() { return value_++; }
};

The g++ error is:

bug_const.cpp: In member function ‘int Counter::total() const’:
bug_const.cpp:3:45: error: passing ‘const Counter’ as ‘this’ argument discards qualifiers [-fpermissive]
    3 |     int total() const { return value_ + bump(); }
      |                                         ~~~~^~
bug_const.cpp:6:9: note:   in call to ‘int Counter::bump()’
    6 |     int bump() { return value_++; }
      |         ^~~~

The fix for the trie is the one used in walk. It reads the nodes and does not change them, so it is const and can be called from contains and count.

Inserting only the whole text

The most common mistake is to insert the text as one word and nothing else. That trie answers true only for the full text and its prefixes. For banana, the query nan is false, although nan is in the text. The fix is to insert every suffix, as build does with a loop over start positions.

Counting nodes instead of passes

A node exists for every substring, so checking that a node exists answers the yes or no question. The count of occurrences is a different number. It is the number of suffixes that pass through the node, which is stored in passes. Returning 1 whenever the node exists gives the wrong count for any pattern that appears more than once.

Using uppercase letters

The slot index is c - 'a', so an uppercase letter gives a negative index. The array trie lesson shows the assertion message this produces. Lowercase the text and the pattern before building or querying, or reject other letters first.

Practice

Exercise 1: Count the occurrences

Using the class above, how many times does an occur in banana? List the starting positions.

Show the answer

It occurs twice, at positions 1 and 3. Position 1 is the a after b, followed by n. Position 3 is the a after the second n, followed by n. The passes count on the an node is 2.

Exercise 2: Predict a result

For the text banana, predict the output of contains("nab") and contains("nan"). Then check your answer by running the program.

Show the answer

The first is false, because no suffix starts with nab. The second is true, because nan is the start of the suffix nana. The program prints false and true in its output.

Exercise 3: Count overlapping matches

How many times does aa occur in aaaa? How many times does aaa occur?

Show the answer

aa occurs 3 times, at positions 0, 1 and 2. aaa occurs 2 times, at positions 0 and 1. The class returns these numbers when it is built on aaaa.

Exercise 4: Count the nodes

The class builds one node per distinct substring plus one for the root. How many nodes does the trie for abab have? The distinct substrings are a, b, ab, ba, aba, bab and abab.

Show the answer

The trie has 8 nodes, 7 for the distinct substrings and 1 for the root. Running the class on abab gives the same number.

Exercise 5: Estimate the memory

A text of length 10,000 where almost every substring is different needs at most n(n+1)/2 nodes. Using the 108 bytes per node in this layout, how many bytes does the trie need? Give the answer in gigabytes, rounded to one decimal place.

Show the answer

The node count is at most 10,000 times 10,001 divided by 2, which is 50,005,000. Multiplying by 108 gives at most 5,400,540,000 bytes. That is about 5.4 GB for one structure.

Summary

• A pattern is a substring of a text exactly when it is a prefix of one of the text's suffixes.
• Build the trie by inserting every suffix, then answer queries by walking the pattern through the trie.
• Each node's passes count is the number of starting positions of the pattern that leads to it, and that count includes overlapping matches.
• The trie has one node per distinct substring plus the root, so it grows with the square of the text length.
• A query costs time in the pattern's length, but the build and the memory cost grow with the square of the text length.
• For long texts, a suffix array or a suffix tree stores the same information in much less memory.