Suffix Tree: Every Suffix of a Text in One Tree

A suffix tree is a compact index for every suffix of a text. Its central idea is straightforward: write down all suffixes, place them into one trie-like structure, and merge paths whenever suffixes begin with the same characters.

The example banana$ makes the idea especially visible. The character $ is a unique end marker. It is not an ordinary character in the text; it marks the end and ensures that every suffix has an explicit endpoint.

Once the tree has been built, a pattern can be searched by following one path from the root. For the pattern ana, that path leads to two suffixes: the suffix beginning at position 2 and the suffix beginning at position 4. Therefore, ana occurs at positions 2 and 4 when positions are counted from 1.

This article explains that process carefully and then compares suffix trees with related text-indexing techniques: KMP, Boyer–Moore, Rabin–Karp, Manacher’s algorithm, tries, and radix trees. All of these techniques reduce repeated work, but each remembers a different kind of structure.

1. The basic problem: searching without starting over​

Suppose a text contains many characters and we want to answer questions such as:

• Does a pattern occur?
• Where does it occur?
• Which suffixes begin with a given pattern?
• Which stored strings share a prefix?
• Is a substring a prefix of one or many stored strings?

A direct search can compare a pattern with the text at every possible starting position. For the text banana and pattern ana, we could try the pattern at position 1, then position 2, then position 3, and so on.

That method can repeat comparisons. If several characters match at one location and a later character fails, a simple scanner may discard the information it already learned when it moves to the next location. More sophisticated algorithms avoid this waste by remembering useful structure.

A suffix tree remembers structure across all suffixes of the text. Instead of searching the original text from scratch for every query, it organizes the text once and lets later queries reuse that organization.

This is the most important design choice to understand:

• A one-off search usually performs work while scanning.
• An indexed approach performs more work during construction so that later searches can be faster or more informative.

2. What is a suffix?​

A suffix is a substring that begins at some position and continues all the way to the end of the text. For banana$, the suffixes are:

banana$
anana$
nana$
ana$
na$
a$
$

The first suffix begins at position 1, the second at position 2, and so on. The final suffix consists only of the end marker.

The end marker is important. Without it, one suffix could end while another continues, making the tree representation less explicit. With $, every suffix has a clear endpoint, and $ does not occur anywhere else in the indexed text.

A suffix tree stores these suffixes in a compressed trie. A regular trie normally represents one character per edge. A suffix tree can combine a chain of single-child nodes into one edge labeled by a whole substring.

For example, if a path has no branch between its beginning and its end, an implementation need not store separate edges for b, a, n, a, n, a, and $. It can store one edge labeled banana$, or represent that label by a start and end boundary in the original text.

3. Building the tree from banana$​

Begin with the suffixes listed above. If every suffix were inserted into an ordinary trie, suffixes with common beginnings would naturally share paths.

The suffixes beginning with a are:

anana$
ana$
a$

They share the first character a. The first two also share na after that first character, while the final suffix ends after a.

The suffixes beginning with n are:

nana$
na$

They share the initial na. After that shared part, one continues with na$ and the other ends.

A conceptual top-level view looks like this:

root
├── banana$
├── an...
├── n...
├── a$
└── $

The diagram is intentionally abbreviated. The important point is that suffixes beginning with the same characters follow the same path until they differ or one suffix ends.

The repeated substring ana shows the benefit particularly well. It is present in the suffix beginning at position 2, anana$, and in the suffix beginning at position 4, ana$. The two suffixes share the path labeled ana.

After that path, their remaining text differs:

suffix at position 2: ana + na$
suffix at position 4: ana + $

Consequently, the path for ana branches. One continuation is na$; the other is $. The leaves below the branch carry the starting positions 2 and 4.

A compact local view is:

ana
├── na$   position 2
└── $     position 4

This is not a complete drawing of the entire tree, but it captures the part needed to understand the query.

4. Searching for ana​

To search for ana, start at the root and consume the pattern characters along the tree edges:

1. Follow an edge beginning with a.
2. Consume n.
3. Consume the next a.
4. Stop after all pattern characters have been consumed.

The search has reached the locus of ana: the point in the tree representing that string. Every leaf below this point corresponds to a suffix that begins with ana.

Those leaves are:

anana$   position 2
ana$     position 4

Therefore, the occurrences are at positions 2 and 4.

The query does not compare ana independently with every text position. It follows the already-built shared path once. The leaves beneath that path provide the occurrence positions.

This is the key difference between a suffix tree and a one-off scan. Construction performs organizational work up front. Later substring queries reuse the organization.

The pattern does not have to end exactly at a leaf. It can end in the middle of a compressed edge. What matters is that all pattern characters have been consumed. If the pattern path exists, the leaves below that point represent matching suffixes.

5. Why the shared path matters​

Consider the two suffixes anana$ and ana$. A naive representation stores the characters independently:

anana$
ana$

A shared representation stores their common beginning once:

ana
├── na$
└── $

The characters a, n, and a are not duplicated at the branching point. This is the same broad principle used by tries and radix trees: common prefixes should be represented once and reused.

For a query such as an, the tree follows a and then n. The suffixes beginning at positions 2 and 4 remain below that point, so both positions can be reported.

For a query such as banana, the tree follows the path beginning at the root and reaches the suffix at position 1. For a query such as xyz, there is no matching first edge, so the search fails immediately.

A suffix-tree query therefore has two basic outcomes:

• The path does not exist, so the pattern is absent.
• The path exists, and the leaves below it identify all matching locations.

6. The role of the end marker​

The $ in banana$ is a sentinel: a special character used only to mark the end of the text.

It distinguishes the suffix a$ from the suffix ana$. It also makes every suffix terminate explicitly. If the text ended without a unique marker, a shorter suffix could be a prefix of a longer suffix, requiring special handling at an internal point.

The marker must be unique. If $ appeared as an ordinary character inside the text, it would no longer unambiguously mean the end. Another character could be used in a different application, provided it does not occur in the input alphabet.

When matches are reported, the sentinel is normally an implementation detail. A query for ana matches the ordinary characters a, n, and a; $ organizes the suffixes but is not part of the requested word.

The complete indexed text and the searchable text are therefore slightly different concepts. The tree may include a sentinel to make the representation well-defined, while application-level queries usually ignore it.

7. Complexity and construction trade-offs​

The exact complexity depends on the construction method and representation. In the standard theoretical model, a suffix tree for a text of length $n$ can be built in linear time and linear space, $O(n)$, using suitable algorithms and assumptions about the alphabet.

A query for a pattern of length $m$ can locate its path in time related to $m$, often written as $O(m)$ for traversal, plus the cost of reporting matches. If the pattern occurs at $k$ positions, returning those positions requires additional output time. In that case, the total query cost is commonly described as $O(m + k)$ when the structure can enumerate the matching leaves efficiently.

The output term matters. A data structure may find the relevant subtree quickly, but it cannot return $k$ separate positions in less than the time needed to produce those results.

These bounds describe the data-structure goal, not every possible implementation. A straightforward educational construction that inserts every suffix one at a time may perform more work than a specialized linear-time construction. The shared-path idea remains the same even when the construction method differs.

A practical representation also affects memory. Storing a separate string on every edge can duplicate characters. Instead, an edge label can be represented by two boundaries into the original text: a starting index and an ending index. The tree then stores references to text rather than copies of text.

The alphabet representation matters too. Each node needs a way to locate the outgoing edge for the next character. An array can provide fast access when the alphabet is small and fixed, while a map can save space when outgoing characters are sparse. These choices change constant factors and practical memory usage even when the asymptotic bound is unchanged.

8. Suffix trees versus ordinary tries​

A trie stores a collection of strings by sharing their prefixes. Suppose a dictionary contains:

car
card
care
cat

The strings car, card, and care share car, while cat shares only ca. A trie represents each shared prefix as one path.

A suffix tree applies a similar idea to every suffix of one text. Its input collection is not a dictionary selected by a user; it is the set of all suffixes of the text.

The distinction is useful:

• A trie is naturally designed for a set of stored strings.
• A suffix tree is naturally designed for substring queries in one text.
• A suffix tree answers a substring query by treating the query as a path from the root.
• A trie usually answers prefix queries, while a suffix tree turns substrings into prefixes of suffixes.

That last point explains the power of suffix trees. A substring beginning at position $i$ is a prefix of the suffix that begins at $i$. Searching for a substring is therefore equivalent to finding suffixes with that prefix.

For example, ana is not a prefix of the entire text banana, but it is a prefix of the suffixes anana$ and ana$. The suffix tree exposes those suffixes as a shared path.

9. Radix trees: compressing chains​

A radix tree, also called a compact trie in many contexts, compresses paths where intermediate nodes have only one child. Instead of storing one character on every edge, it stores a string segment.

For example, a chain spelling banana$ can become one edge labeled banana$ until a branching point is needed. If another string shares ban, the edge may be split:

ban
├── ana$
└── d...

Suffix trees use this compressed-path principle extensively. Edge labels can be substrings of the original text rather than newly copied strings. An implementation can store a pair of boundaries, such as a start index and an end index, instead of storing every edge label separately.

This representation saves space and makes long nonbranching portions easier to traverse. It also shows why a suffix tree is more than a plain list of suffixes: it is a compact hierarchy of shared prefixes.

A radix tree is especially useful when stored strings have long common prefixes. It reduces the number of intermediate nodes and can make prefix lookup practical for dictionaries, routing tables, and autocomplete data. A suffix tree uses the same compression idea, but the strings being indexed are all suffixes of one text.

10. KMP: remembering pattern prefixes​

The Knuth–Morris–Pratt algorithm solves a different version of the repeated-work problem. It searches for one pattern in one text without building a suffix tree for the entire text.

KMP preprocesses the pattern and records how much of the pattern is also a proper prefix of itself. This information is often called a failure function or prefix-function table.

Take the pattern abab. Its prefixes that are also suffixes include:

pattern: a b a b
position 1: none
position 2: none
position 3: a
position 4: ab

Suppose a comparison fails after KMP has matched ab. The matched text ends with ab, and ab is also the beginning of the pattern. KMP does not need to restart with no information. It can reuse that known prefix relationship.

More generally, if the algorithm has matched $j$ characters and the next comparison fails, the prefix table tells it which shorter prefix might still match the suffix of the text already examined. The text index does not move backward simply because the pattern has fallen back.

The standard KMP search runs in $O(n + m)$ time for text length $n$ and pattern length $m$, with $O(m)$ additional space for the pattern table. Its trade-off is that it is excellent for a single exact pattern search, but it does not provide the broad index of all substrings that a suffix tree provides.

The connection to suffix trees is conceptual. KMP preserves prefix information inside one pattern. A suffix tree preserves shared prefixes among all suffixes of a text.

11. Boyer–Moore: shifting past known mismatches​

Boyer–Moore also avoids repeated comparisons, but it usually compares the pattern from right to left. When a mismatch occurs, the algorithm uses information about the mismatching character or the pattern’s already matched suffix to shift the pattern by more than one position.

For a simple illustration, suppose the pattern is:

needle

If the text window ends with a character that does not occur in needle, the entire window may be skipped. There is no reason to align the pattern at each intervening position, because that mismatching character cannot match any character in the pattern.

Other shifts use characters that do occur in the pattern or suffixes that have already matched. The exact shift depends on the Boyer–Moore rules and preprocessing tables being used.

Boyer–Moore can be very effective in practical text search, especially when the pattern is reasonably long and the alphabet is varied. Its behavior depends on the pattern, alphabet, and algorithmic variant. Strong worst-case guarantees require particular refinements, while practical implementations often emphasize large average-case skips.

Compared with a suffix tree, Boyer–Moore does not build a permanent index of the text. It prepares the pattern, then scans the text. A suffix tree prepares the text, then can answer many pattern queries.

This leads to a practical rule:

• Use a pattern-oriented algorithm when the text will be scanned for a small number of patterns.
• Consider a text index when the same text will receive many different substring queries.

12. Rabin–Karp: comparing fingerprints first​

Rabin–Karp avoids repeatedly comparing every character by assigning a numeric fingerprint, or hash, to a window of text. It compares the pattern’s hash with the current window’s hash. If the hashes differ, the strings definitely differ. If the hashes agree, the characters can be checked to guard against a collision.

The rolling part means that the next window’s hash is updated from the previous window instead of recomputed from scratch. For a window of length $m$, a polynomial-style hash can be represented conceptually as:

When the window moves one character to the right, the outgoing character is removed, the remaining value is shifted, and the new character is added. In modular arithmetic, the update has the general form:

Here $b$ is a chosen base and $q$ is a modulus. The exact details vary by implementation.

For example, the length-three windows in banana are:

ban
ana
nan
ana

The hash for one window can be updated to obtain the next window’s hash without rebuilding the value from all three characters. The outgoing character is removed, the remaining value is shifted, and the incoming character is incorporated.

Rabin–Karp is useful for comparing many patterns, detecting duplicate substrings, and searching with fingerprints. Its trade-off is hashing risk: equal hashes do not necessarily prove equal strings unless the characters are verified or a sufficiently robust hashing strategy is used.

With appropriate assumptions, expected performance can be close to linear for a single search. Worst-case behavior can be worse when many collisions cause repeated character verification.

The shared idea with suffix trees is reuse. Rabin–Karp reuses a numerical summary of overlapping windows; a suffix tree reuses shared paths among suffixes.

13. Manacher’s algorithm: reusing palindrome radii​

Manacher’s algorithm targets a specialized problem: finding palindromic substrings efficiently. A palindrome reads the same from left to right and right to left, such as aba or anana.

A naive palindrome search expands around every possible center. If one center produces a long palindrome, a later center may repeat many of the same character comparisons. Manacher’s algorithm stores palindrome radii and uses the symmetry of a known palindrome to initialize information for a mirrored center.

In banana, the substring anana is a palindrome. Its center is the middle n in that substring. Once the algorithm knows the palindrome’s boundaries, a center reflected across the main center can inherit a radius limited by the known boundary. It expands only when necessary.

The standard algorithm finds all palindromic radii in $O(n)$ time and uses $O(n)$ space. It is highly specialized: it does not replace a general substring index, but it is an excellent example of avoiding repeated work through previously computed structure.

The connection to suffix trees is structural rather than identical. A suffix tree reuses shared prefixes. Manacher’s algorithm reuses symmetry and previously known expansion boundaries.

14. Comparing the techniques​

The techniques differ mainly in what they preprocess and remember.

A suffix tree spends substantial effort organizing the text. KMP, Boyer–Moore, and Rabin–Karp typically spend less effort preparing one pattern and then scan the text. A trie or radix tree is usually built for a collection of strings and is especially good when the query is a prefix. Manacher’s algorithm is narrower but gives a strong linear-time solution for palindromes.

No technique is universally best. The right choice depends on whether the workload has one query or many, whether queries are exact or prefix-based, whether the text changes frequently, and whether memory is limited.

15. Practical use: a text-search index​

A suffix tree is most attractive when the same text receives many substring queries. Examples include searching a document, finding repeated phrases, locating all occurrences of a term, or supporting analyses that ask about many substrings.

For banana$, a query for ana follows one path and then enumerates the leaves below it. A query for na reaches a higher point and reports positions 3 and 5. A query for banana reaches the suffix beginning at position 1. A query for band fails when the path diverges after the shared beginning ban.

The cost of reporting matters. If a pattern occurs at $k$ positions, the result itself contains $k$ positions. Even if path traversal is fast, returning all results takes at least $O(k)$ time simply to produce them.

This output-sensitive behavior is common in indexing. Finding the location of a path and listing everything below it are separate tasks.

A production search system may also store extra information at internal nodes, such as counts or references to documents. Those additions can make common operations faster, but they also increase construction and storage requirements. The essential suffix-tree operation remains the same: follow the pattern path and inspect the suffixes below it.

16. Practical use: search boxes and autocomplete​

Autocomplete usually asks for strings beginning with the user’s current input. If the user types car, the system wants candidates such as car, card, and care.

A trie or radix tree is a natural structure for this task because the query is a prefix of the stored words. The system follows the path for c, then a, then r, and retrieves suggestions below that node.

A suffix tree can also be viewed through the same shared-prefix lens, but its typical purpose is different: it indexes every suffix of a text rather than only a curated dictionary of suggestion strings. For a word-oriented autocomplete dictionary, a trie or radix tree usually matches the data model more directly.

For a search box over document text, a suffix-based index can help locate substrings that may occur in the middle of words or phrases. KMP, Boyer–Moore, and Rabin–Karp are generally more appropriate for scanning when a query arrives than for storing a large persistent prefix index. Manacher’s algorithm is relevant only when the search specifically asks for palindromic content.

The practical distinction is therefore about query shape:

• Autocomplete asks what stored strings begin with this prefix.
• Substring search asks where this pattern occurs inside a text.
• A suffix tree turns the second question into a prefix lookup among suffixes.

17. Construction and query trade-offs​

The most important suffix-tree trade-off is preprocessing versus query speed.

If the text is indexed once and searched many times, construction cost can be worthwhile. The tree stores relationships among all suffixes, so repeated queries can reuse those relationships.

If the text changes after every query, maintaining a suffix tree may be more complicated than scanning the current text. Similarly, if memory is severely constrained, another index may be preferable, although the choice depends on the application.

The representation matters. Storing a separate string on every edge can duplicate characters and consume unnecessary memory. Storing references into the original text allows an edge label to be described by boundaries. A compressed tree can represent long nonbranching regions efficiently, but the implementation must correctly handle edge offsets and branching points.

The alphabet matters as well. Each node needs a way to locate the outgoing edge for the next character. An array can provide fast access when the alphabet is small and fixed, while a map can save space when outgoing characters are sparse.

There is also a maintenance question. A suffix tree is most natural for a fixed or slowly changing text. A dictionary trie or radix tree may be easier to update as words are added and removed. A pattern-search algorithm such as KMP may be simpler when there is only one query and no reason to retain an index.

18. A careful walk through banana$​

It is useful to summarize the entire example without hiding the important steps.

The text is:

b a n a n a $
1 2 3 4 5 6 7

The suffixes are:

1: banana$
2: anana$
3: nana$
4: ana$
5: na$
6: a$
7: $

Now focus on the pattern ana.

The suffix at position 2 begins with ana:

anana$

The suffix at position 4 also begins with ana:

ana$

The suffixes at positions 1, 3, 5, 6, and 7 do not begin with all three characters ana.

The tree merges the common path:

ana
├── na$   position 2
└── $     position 4

Following a, then n, then a reaches the shared path. Reading the leaf labels below it gives 2 and 4. Thus:

The end marker is included in the indexed text so the suffixes terminate cleanly, but it is not part of the requested pattern.

Notice what the tree has avoided. It has not created two unrelated routes for the two occurrences of ana. The routes meet for their shared characters and branch only when their remaining suffixes differ.

19. A useful mental model: suffixes turn substrings into prefixes​

The most reusable mental model is:

Every substring is a prefix of some suffix.

The occurrence ana beginning at position 4 is a prefix of the suffix ana$. The same substring beginning at position 2 is a prefix of anana$.

A suffix tree does not need a separate mechanism for every possible substring. It stores suffixes and their shared prefixes. A substring query becomes a path query.

This transformation explains why the structure can answer questions about arbitrary internal pieces of the text. Once a substring is viewed as the beginning of a suffix, ordinary shared-prefix machinery becomes applicable.

It also explains the relationship with tries. A trie asks which stored strings begin with a query. A suffix tree asks which suffixes begin with a query. Since every occurrence of a substring begins a suffix, the suffixes below the query path identify the occurrence positions.

20. Practical takeaways​

When choosing a text algorithm or index, ask what repeated work is occurring.

• If many suffixes share prefixes, a suffix tree or compressed trie-like structure can merge those paths.
• If one pattern has self-overlapping prefixes, KMP can remember how far the pattern may fall back.
• If mismatches make large skips possible, Boyer–Moore can shift the pattern instead of moving one character at a time.
• If overlapping windows can be summarized numerically, Rabin–Karp can update rolling hashes instead of recomputing them.
• If palindrome centers mirror one another, Manacher’s algorithm can reuse known radii.
• If many stored words share prefixes, a trie or radix tree can support lookup and autocomplete efficiently.

For the specific example banana$, the central lesson is the shared path ana. The two occurrences do not require two unrelated search paths in the index. They meet at one path and separate only where their remaining suffixes differ. Following that path leads to positions 2 and 4.

That is the essence of a suffix tree: represent every suffix in one shared, compressed tree so that later substring queries can reuse the structure rather than repeating the same comparisons.