Suffix Tree: How to Instantly Find Repeated Text Fragments

A suffix tree is a tree-shaped index of all suffixes of a text. Its central idea is simple: list every suffix, group suffixes that begin with the same characters, and store each shared beginning only once. When several suffixes have a common prefix, they follow the same path from the root until their remaining text differs or one suffix ends.

The example banana$ is small enough to inspect by hand and rich enough to show the important behavior. It contains repeated fragments such as ana and na. In a suffix tree, those repeated fragments appear as paths shared by multiple suffixes. A substring query such as ana can then follow the characters a, n, and a through the tree instead of treating every possible starting position as a completely separate comparison.

The $ character is a special terminal marker. It is not part of the original word banana; it makes the end of the text explicit and ensures that every suffix has a distinct ending. With that marker in place, the tree can represent both a suffix that ends after a particular character and a longer suffix that continues with the same characters.

This article builds the suffix tree conceptually, explains its invariants, walks through the banana$ structure, demonstrates substring queries, and shows how shared paths reveal repeated text fragments.

1. What is a suffix?​

A suffix is a substring that starts at a position in the text and continues all the way to the end. Consider the text:

banana$

Using zero-based positions, its characters are:

position:  0 1 2 3 4 5 6
character: b a n a n a $

There is one suffix beginning at every position:

The final suffix is simply $. Including it is important: the terminal symbol is part of the indexed representation, so the text has a suffix beginning at its last position as well.

A suffix tree stores these seven suffixes together. It does not store them as seven unrelated strings. Instead, it organizes them according to their initial characters and merges common prefixes.

For example, the suffixes anana$ and ana$ both begin with ana. Their paths should therefore share the characters a, n, and a. They differ afterward: ana$ reaches the end marker, while anana$ continues with na$.

2. From a list of suffixes to a tree​

Imagine inserting every suffix into a trie. A trie has one step for each character, and strings with the same beginning follow the same nodes. A suffix tree uses the same shared-prefix idea but compresses chains that do not branch.

At the root of the banana$ tree, suffixes begin with four different symbols:

• b begins the suffix banana$.
• a begins the suffixes anana$, ana$, and a$.
• n begins the suffixes nana$ and na$.
• $ begins the suffix $.

Therefore, the root has four conceptual outgoing paths: one beginning with b, one with a, one with n, and one with $.

The path beginning with b belongs to only one suffix. Since no other suffix begins with b, the entire remaining text can be represented as one compressed edge labeled banana$.

The a path is more interesting. Three suffixes begin with a, and two of them share the longer prefix ana. The tree preserves the shared portion and branches when the suffixes have different continuations.

The n path behaves similarly. The suffixes nana$ and na$ share na, then one ends while the other continues.

A compact conceptual representation is:

root
├── $
├── banana$
├── a
│   ├── $
│   └── na
│       ├── $
│       └── na$
└── n
    └── a
        ├── $
        └── na$

The exact placement of compressed edge boundaries can vary in a drawing, but the shared-prefix relationships must remain the same. The a branch represents the suffixes:

a$
ana$
anana$

All three share the first a. The two longer suffixes share an, then both continue through ana. At that point, one reaches $ and the other continues with na$.

The n branch represents:

na$
nana$

Those suffixes share na, after which one ends and the other continues.

3. The role of the terminal symbol $​

The terminal marker makes suffix boundaries visible. Without it, a shorter suffix could be a prefix of a longer suffix, which would make the structure less explicit.

For example, the suffixes in the unmarked word banana include:

banana
anana
nana
ana
na
a

The suffix a ends immediately, while other suffixes beginning with a continue. Adding $ changes them to:

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

Now the suffix a$ clearly says that the text ends immediately after the a. The suffix ana$ shares the beginning a and then n and a, but it reaches the terminal marker later. The two suffixes can therefore be represented as different paths after their shared portion.

The marker also gives the final suffix its own path:

root → $

In the tree, a leaf represents the end of a complete suffix. The terminal symbol ensures that suffix endings are represented explicitly, even when one suffix is a prefix of another suffix.

For ordinary substring queries over the original word, $ is usually treated as an implementation marker rather than a character users search for. It is still essential to the structure because it distinguishes the endpoints of suffixes.

4. The central suffix-tree invariant​

The most important invariant is:

Every suffix of the text corresponds to a path from the root to a leaf, and the characters along that path spell the suffix.

For banana$, there must be seven suffix paths, one for each starting position. The leaf for banana$ represents position 0, the leaf for anana$ represents position 1, and so forth through the leaf for $ at position 6.

A second invariant describes prefix sharing:

If two suffixes have the same prefix, their paths share the corresponding characters for as long as that prefix remains identical.

Thus, anana$ and ana$ must share the path for ana. The suffixes na$ and nana$ must share the path for na.

A third useful rule explains branching:

Branching occurs where suffixes have different next characters or where one suffix ends while another continues.

This rule explains the shape of the a branch. The suffixes a$, ana$, and anana$ share a, but a$ ends at that point while the other two continue with n. The tree needs one continuation for $ and another for n.

These invariants are more important than any particular diagram style. A drawing is correct if every suffix has a root-to-leaf path and common prefixes are shared until the suffixes diverge or end.

5. Walking through the a branch​

The a branch contains the clearest example of repetition. The suffixes beginning with a are:

a$
ana$
anana$

All three begin with:

a

One suffix, a$, ends immediately after that character. The other two continue with n, so the tree must distinguish these alternatives.

The continuing suffixes are:

ana$
anana$

They share ana. After that shared fragment, the shorter suffix reaches $, while the longer suffix continues with na$.

The relevant shape can be shown as:

          a
          |
          n
          |
          a
        /   \
       $    na$

The initial a$ suffix creates an additional ending choice at the earlier a position. Conceptually, the complete branch is:

root
└── a
    ├── $
    └── n
        └── a
            ├── $
            └── na$

The path a → n → a is shared by the suffixes anana$ and ana$. The two different continuations identify two different suffix starts.

This is the structural reason that ana is repeated in banana. The tree does not need to store two independent copies of the fragment. It stores one shared path and preserves the distinct suffix endings below it.

6. Walking through the n branch​

The suffixes beginning with n are:

na$
nana$

They share the prefix na. One suffix ends after this prefix, and the other continues with na$:

          n
          |
          a
        /   \
       $    na$

This branch shows that na is also repeated. It occurs at positions 2 and 4 in the original text:

b a n a n a
    ^ ^

More precisely, the occurrence beginning at position 2 is the prefix of nana$, and the occurrence beginning at position 4 is the prefix of na$.

The a and n branches are separate because the first character of the relevant suffixes differs. Within each branch, however, the suffix tree continues to merge identical beginnings.

7. How the repeated fragment ana appears​

The fragment ana occurs twice in banana, beginning at positions 1 and 3:

b a n a n a
  a n a
      a n a

The suffix beginning at position 1 is:

anana$

The suffix beginning at position 3 is:

ana$

Both suffixes begin with the same three characters:

ana

Consequently, they follow the same path from the root:

root → a → n → a

After the query has consumed ana, the two suffix paths separate. One reaches $; the other continues with na$. The path has two descendant leaves, corresponding to starting positions 1 and 3.

This gives a general way to interpret repeated fragments:

A path shared by multiple suffixes represents a prefix that occurs at multiple starting positions in the text.

The longer the shared path, the longer the repeated fragment. For this example:

• a is shared by suffixes starting at positions 1, 3, and 5.
• an is shared by suffixes starting at positions 1 and 3.
• ana is shared by suffixes starting at positions 1 and 3.
• na is shared by suffixes starting at positions 2 and 4.

The tree makes these repetitions visible through its branching structure and descendant leaves.

8. Querying a substring by following a path​

A substring query asks whether a pattern occurs in the text. To search for a pattern, begin at the root and consume its characters from left to right.

Consider:

pattern = ana

Match the first character​

The first required character is a. The root has a path beginning with a, so follow it.

Match the second character​

The next required character is n. The a path continues with n, so the query can continue.

Match the third character​

The next required character is a. The path continues again. All three query characters have now been consumed.

The query succeeds because ana appears along a continuous path from the root. The matching path has descendant leaves for anana$ and ana$, so it identifies the two corresponding occurrence positions, 1 and 3.

The query does not need to finish at a leaf. A substring can end before the corresponding suffix ends. For example, ban is a substring because it is a prefix of the suffix banana$, even though the suffix continues with ana$.

A query can also finish in the middle of a compressed edge. Edge labels may contain several characters, so the search compares the query with the characters on the edge and can stop once the entire pattern has been matched.

9. A query that fails​

Now search for:

pattern = anb

The tree can follow a, then n. At the next step, however, the relevant path does not continue with b. No suffix begins with anb, so the query fails.

Another failed query is:

pattern = nab

The tree follows n, then a, but no matching b continuation exists after that prefix.

The failure rule is straightforward: if the next query character cannot be matched on the current path, no suffix has the requested prefix, and the pattern does not occur in the text.

This is the practical advantage of organizing suffixes by shared beginnings. A failed query can stop as soon as the tree has eliminated every possible suffix continuation.

10. Substrings versus suffixes​

A suffix always extends to the end of the text. A substring can end anywhere. This distinction is essential when using a suffix tree.

For banana$, the following is a suffix:

anana$

But this is only a substring:

ana

The substring ana is found as a prefix of two complete suffixes. It does not have to include the remaining na$ from the longer suffix, and it does not have to include $ from the shorter suffix.

If a search algorithm required every successful pattern to end at a leaf, it would incorrectly reject many valid substrings. The correct condition is that all pattern characters can be consumed along a path. Once the pattern is fully matched, the query has succeeded, even if the path continues.

The terminal symbol is useful for exact suffix-boundary questions. For example, ana$ identifies the complete suffix beginning at position 3. An ordinary query for ana, by contrast, should stop before the marker and report both relevant suffix starts.

11. Compressed edge labels​

A suffix tree is often described as a compressed trie. The difference is that a trie uses one node or edge step per character, while a compact suffix tree can store a sequence of characters on one edge when no branching occurs inside that sequence.

For example, the suffix banana$ begins with b, and no other suffix begins with b. There is no reason to create separate branching nodes for b, a, n, a, n, a, and $ if the path has no alternative along the way. The entire sequence can be represented by an edge labeled:

banana$

The same compression can be applied to unique continuations below shared prefixes. A path must remain logically equivalent to the original sequence of characters, but intermediate one-child nodes can be omitted.

When reading an edge-labeled tree, remember that a node boundary does not necessarily occur after every character. The search compares the query with the full edge label. A pattern may end inside that label and still be a valid substring.

Compression changes the visual size of the tree, not its meaning. The root-to-leaf path still spells a complete suffix, and shared prefixes are still represented once.

12. What leaves and descendant leaves mean​

Each leaf corresponds to one suffix and therefore to one starting position in the text. A practical implementation associates the suffix's starting index with its leaf.

For banana$, the associations are:

banana$ → position 0
anana$  → position 1
nana$   → position 2
ana$    → position 3
na$     → position 4
a$      → position 5
$       → position 6

When a query path is matched, its descendant leaves identify suffixes that begin with the query. Those suffix starts are exactly the positions where the substring occurs.

For ana, the descendant leaves correspond to:

anana$ → position 1
ana$   → position 3

Therefore, ana occurs at positions 1 and 3.

The leaf does not represent every substring occurring at that position. It represents the complete suffix starting there. The query path selects the prefix of that suffix, and the leaf tells us where that prefix begins in the original text.

This distinction separates two operations:

1. Existence testing: determine whether a path for the pattern exists.
2. Occurrence reporting: collect the starting positions of descendant leaves below the matched path.

A pattern may be easy to confirm but require additional work to report many occurrence positions.

13. Internal paths and repeated prefixes​

An internal path is useful because it can be shared by several suffixes. If multiple leaves remain below a path, the string spelled along that path occurs at multiple starting positions.

For example, the path ana has two descendant leaves. Therefore, ana is repeated. The path a has three relevant descendant leaves, so a appears three times as a suffix prefix. The path na has two descendant leaves, so na appears twice.

The tree does not need a separate object for every possible substring. Many substrings are represented implicitly as prefixes of root-to-leaf paths. A shared path gives the relationship between the fragment and the suffix starts that contain it.

A branch is especially informative because it shows that the same prefix has different continuations. At ana, one suffix ends and another continues. That divergence is enough to show that the path corresponds to more than one suffix.

This is also why internal structure can be used to reason about repeated text fragments. Follow a path from the root and ask how many leaves are below it. If more than one leaf is reachable, the path label is shared by multiple suffixes.

14. A conceptual insertion process​

One way to understand how the shape arises is to imagine inserting the suffixes one at a time.

Start with an empty root and insert one suffix, such as anana$. It creates a path representing that suffix. When ana$ is inserted, its first characters match the existing path:

ana

At that point, the new suffix ends while the existing suffix continues with na$. The shared path must be preserved, and two continuations must be represented:

ana → $
    → na$

Now insert a$. It shares only the first a with the longer suffixes. It ends after that character, so the a region needs an additional $ continuation.

The same logic applies to the n group. Inserting na$ alongside nana$ creates a shared na path with one ending continuation and one longer continuation.

This is the structural rule behind suffix-tree construction: reuse a matching prefix, then branch at the first point where the new suffix and existing suffixes have different next symbols or different endpoints. The description is conceptual and independent of a particular construction algorithm.

15. Repeated fragments can overlap​

The occurrences of ana in banana overlap. One starts at position 1 and the other at position 3. A suffix tree handles this naturally because it indexes suffixes by starting position rather than trying to divide the text into non-overlapping pieces.

The two relevant suffixes are:

position 1: anana$
position 3: ana$

Their common beginning is still ana, even though the occurrences overlap in the original word. Nothing special has to be added to the tree to support this case. Prefix sharing captures the relationship directly.

This is an important mental model: a suffix tree is not simply a collection of repeated words. It is a map of all suffix beginnings. Every substring is considered as a prefix of one or more suffixes, so overlapping occurrences fit the same representation as non-overlapping occurrences.

16. More example queries​

The banana$ tree supports several useful examples.

Query a​

The root has an a path, so the query succeeds. The suffixes beginning at positions 1, 3, and 5 begin with a, giving three occurrences.

Query an​

Follow a, then n. The path succeeds, and the relevant suffixes begin at positions 1 and 3.

Query ana​

Follow a, n, and a. The path succeeds, with occurrences at positions 1 and 3.

Query na​

Follow n, then a. The path succeeds, with occurrences at positions 2 and 4.

Query nana​

Follow the path beginning with n, then a, n, and a. The query succeeds because it is a prefix of nana$, which starts at position 2.

Query banana​

Follow the b path. The query succeeds because it is a prefix of banana$, which begins at position 0.

Query nab​

The tree can match n and a, but it has no b continuation there. The query fails.

Query ana$​

If the terminal marker is allowed in the query, this pattern identifies the complete suffix ana$ beginning at position 3. The marker distinguishes that complete suffix from the longer suffix anana$, which has the same beginning ana but continues with additional characters.

17. Why the query can be fast​

The tree's speed comes from organizing suffixes by common prefixes. A direct approach might compare a pattern with many possible starting positions separately. When the text has repeated beginnings, that approach may repeatedly inspect the same characters.

In the suffix tree, a query beginning with a immediately enters the group of suffixes that begin with a. If the next character is n, the possibilities narrow to suffixes beginning with an. If the next character is another a, the possibilities narrow to suffixes beginning with ana.

The search follows the query path rather than restarting an unrelated comparison for each suffix. The exact complexity depends on representation details, including how outgoing edges are selected and how compressed edge labels are compared. The structural point remains the same: shared prefixes are indexed once.

There are two different costs to keep in mind. Testing whether a pattern exists follows the path until the pattern ends or a mismatch occurs. Reporting every occurrence requires visiting or otherwise retrieving the descendant leaves. If a fragment appears many times, producing all of those positions necessarily requires output work.

For the small example, the query ana is both easy to find and easy to report because only two suffix leaves lie below its path.

18. Common mistakes when reading a suffix tree​

Mistake 1: Treating it as a dictionary of complete words​

A suffix tree is built from all suffixes of one text. A substring such as ana may not be a complete leaf string; it can be a prefix shared by several complete suffixes.

Mistake 2: Requiring a query to end at a leaf​

A substring query can end at an internal point or inside a compressed edge. The query ban succeeds even though the suffix path continues to banana$.

Mistake 3: Omitting the terminal marker​

The marker makes suffix endpoints explicit. It distinguishes a$ from the longer suffixes beginning with a and gives $ its own final suffix.

Mistake 4: Assuming every character is a separate node​

A compact suffix tree can store multiple characters on one edge. The important boundaries are where paths branch or where a suffix ends, not necessarily every character position.

Mistake 5: Confusing one shared path with one occurrence​

The path for ana is shared, but it has two descendant leaves. Those leaves correspond to two occurrences, at positions 1 and 3.

Mistake 6: Confusing a suffix with a substring​

anana$ is a suffix. ana is a substring that appears as a prefix of two suffixes. The tree indexes suffixes so that substring queries can use their prefixes.

Mistake 7: Forgetting output cost​

Finding a matching path and listing every matching position are separate tasks. A repeated pattern may have many descendant leaves.

19. A practical checklist for constructing the example​

When checking a suffix tree for banana$, use the following process:

1. Write the indexed text, including $.
2. Number its positions from 0 through 6.
3. List the suffix beginning at every position.
4. Group suffixes by their first character.
5. Share each common prefix.
6. Branch when the next characters differ.
7. Add an explicit terminal continuation when one suffix ends while another continues.
8. Compress one-child chains into edge labels if using a compact representation.
9. Associate each leaf with the starting position of its suffix.
10. Verify that every suffix has one root-to-leaf path.
11. To query a pattern, consume its characters from the root.
12. If the path exists, use descendant leaves to identify occurrence positions.

For the specific query ana, the verification is especially clear. The tree must contain the path a → n → a, and that path must lead to leaves for suffix starts 1 and 3.

20. A compact mental model​

Imagine every suffix as a road leaving the root. Roads with the same initial characters travel together. When their next characters differ, they split. If one road reaches the end while another continues, the terminal marker identifies the ending road.

For banana$:

• One road leaves through b and represents banana$.
• Three roads leave through a and represent anana$, ana$, and a$.
• Two roads leave through n and represent nana$ and na$.
• One road leaves through $ and represents the final suffix.

A query such as ana walks the shared road segment labeled a, n, and a. Once the query has consumed all three characters, every suffix road still below that point is an occurrence location.

A failed query reaches a point where the next required road segment does not exist. That means no suffix has the requested prefix.

This road analogy is useful because it explains both operations at once: queries move down paths, while repeated fragments are paths used by multiple suffixes.

21. Complexity and practical interpretation​

The example demonstrates quick substring querying, but complexity should be described carefully because implementation choices matter. A suffix tree may use different ways to represent outgoing edges, and compressed edges may contain several characters. The cost of matching a pattern depends on the characters that must be checked along the relevant path and on how the next edge is selected.

The structural advantage is that the query does not need to compare against every suffix as if each one were independent. Suffixes with the same prefix are grouped together, so one traversal handles the shared portion once.

Existence testing and occurrence reporting should be considered separately:

• Existence testing asks whether the pattern can be matched along a root-to-tree path.
• Occurrence reporting asks which descendant leaves remain below the matched path.

For ana, existence testing confirms that the path is present. Occurrence reporting returns positions 1 and 3. If a different pattern had many occurrences, the second task would have to return all of those positions.

The compact representation also avoids repeating shared character chains wherever suffixes have the same beginnings. This is the source of both its conceptual clarity and its indexing value.

22. Practical takeaways​

The banana$ example captures the essential behavior of a suffix tree:

• A suffix tree represents every suffix of a text.
• Suffixes with the same beginning share a path from the root.
• Branches appear when suffixes have different continuations or different endpoints.
• The terminal symbol $ makes suffix endings explicit.
• Long chains without branching can be compressed into edge labels.
• The fragment ana follows the path a → n → a.
• That path has descendant leaves for suffix starts 1 and 3.
• Therefore, ana occurs twice in banana.
• A query succeeds when all of its characters can be consumed along a path.
• A query does not need to end at a leaf because a substring may be only a prefix of a suffix.
• Repeated fragments appear as paths shared by multiple suffixes.
• Confirming that a pattern exists and reporting all its positions are separate operations.

The most important idea is the invariant: every suffix starts at the root, and common prefixes are represented only once until the suffixes diverge. Once that invariant is clear, the repeated ana in banana$ becomes easy to understand. The suffixes anana$ and ana$ travel through the same a, n, and a path, and their separate continuations preserve the fact that the fragment begins at two different positions.

Conclusion​

A suffix tree turns a text into a map of suffix beginnings. For banana$, the suffixes anana$ and ana$ share the prefix ana, so the tree stores that fragment as one shared path followed by different continuations. A query for ana follows those three characters from the root, succeeds when the path is fully matched, and can use the descendant leaves to identify the two occurrence positions.

The combination of shared-prefix structure, explicit suffix endings, compressed edge labels, and leaf-associated starting positions explains why suffix trees are useful for repeated-fragment discovery and substring queries. When reading or checking a suffix tree, ask three questions: which suffixes share this path, where do their paths branch, and which leaf positions remain below a matched query? Those questions reveal the tree's shape, its invariants, and the information it provides.