Exercises — Suffix tree (conceptual)

Chop the front letter off repeatedly, keeping the $ on the tail:

That is $n+1=7$ suffixes. Why 7 and not 6? the lone $ is itself a suffix.

Exactly ==$n+1=7$== leaves — one per suffix. The $ guarantees no suffix is a prefix of another, so each suffix ends at its own leaf instead of stopping partway down an edge.

True. A node with only one child carries no decision — during compression it gets swallowed into a single edge. So every surviving internal node is a branching point with $\ge 2$ children.

Start at the root. The first edge whose label starts with n is the one labelled na. Walk it:

• match n ✔, match a ✔ — we are now at the branching node after na.
• next character of $P$ is n. From that node one outgoing edge starts with n (the na$ edge). Match n ✔.

We spelled all of nan. Yes, nan is a substring. Cost $=|P|=3$ character-steps.

Walk a → n → a. This lands you exactly at the branching node whose root-path is ana (look at the yellow node in the figure). Now count the leaves in its subtree. Below ana hang two leaves: one continues na$ (leaf 1, suffix anana$) and one continues $ (leaf 3, suffix ana$). So ana occurs 2 times — at start indices $1$ and $3$. Check: b(anana) → positions 1 and 3, and indeed banana = b an an a, ana sits at index 1 (anana) and index 3 (ana). ✔

Walk n,a,n,a,$. You end at a leaf, leaf number $2$ — because the full suffix nana$ starts at index $2$. Reaching a leaf (not stopping mid-edge) means you spelled an entire suffix.

Find the deepest internal (branching) node measured by string-depth. Branching means $\ge 2$ different continuations exist, so its root-path string occurs $\ge 2$ times. In our tree the deepest branching node has string-depth 3, spelling ana. Therefore the longest repeated substring is ana (it appears at indices 1 and 3, overlapping). Length $=3$.

A rooted tree with $L$ leaves in which every internal node has $\ge 2$ children has at most $L-1$ internal nodes. Here $L=n+1$, so internal nodes $\le n$. Total nodes $\le (n+1)+n===2n+1===O(n)$. Why the $\ge 2$-children rule matters: if single-child chains survived, the count would balloon. Compression enforces the rule, capping the tree at linear size.

Each edge stores its label as two integers $(i,j)$ meaning "the substring $S[i..j]$" — never the copied text. There are $O(n)$ edges (one per non-root node), and $2$ integers per edge, giving $O(n)$ words of storage. The conceptual label may be long (like nana$), but we only ever keep the two endpoints into $S$.

Rule 4: no two edges out of a node start with the same character. The distinct first characters among the suffixes of banana$ are b, a, n, $. So the root has exactly 4 children:

• banana$ → leaf 0 (starts with b, unique, so one long edge to a leaf).
• a… → branching node (suffixes anana$, ana$, a$ all start with a).
• na… → branching node (nana$, na$).
• $ → leaf 6.

Suffixes: aaaa$(0), aaa$(1), aa$(2), a$(3), $(4) → $n+1=5$ leaves. Longest repeated substring: the deepest branching node. The string aaa occurs at indices 0 and 1 (twice), and aaaa occurs once. So the longest repeat is aaa, length $3=n-1$. (For a run of $k$ identical letters, the longest repeat is that run minus one letter.)

Algorithm: start at root, current position = beginning of $P$. Repeatedly: pick the outgoing edge whose label's first character equals $P$'s current character (at most one exists, by rule 4); walk along that edge comparing character-by-character. If any comparison fails, or you run off the end of an edge with no matching next edge, answer no. If you exhaust all of $P$ (whether you stop mid-edge or at a node), answer yes. Cost: you read each character of $P$ at most once → $O(|P|)$, independent of $n$. Edge case that breaks naive testers: stopping inside an edge. nan ends in the middle of an edge but is still a valid substring. A tester that only says "yes" when it lands exactly on a node would wrongly reject nan. Fix: "yes" whenever $P$ is fully consumed, node or mid-edge.

Yes, overlaps are counted. The count = number of leaves below the match = number of suffixes that start with $P$. Suffix anana$ (index 1) and suffix ana$ (index 3) both start with ana, so both leaves are counted — regardless of whether the spans overlap in $S$. The tree counts starting positions, and overlapping matches have distinct starting positions. Answer for ana: 2.

• KMP Algorithm: one pattern, one text, scanned once — $O(n+|P|)$, tiny memory. Use when you search a known text once.
• Suffix Array: same substring power as a suffix tree but a fraction of the memory; search is $O(|P|\log n)$. Use when the text is fixed and queried many times and memory matters.
• Suffix tree: richest structure — $O(|P|)$ search, longest-repeat, Longest Common Substring via a generalized tree — but heaviest memory (large constant). Use when you need those advanced queries and can afford the space.

In any rooted tree, #edges $=$ #nodes $-1$. We proved total nodes $\le 2n+1$, so edges $\le 2n$. For banana$ ($n=6$): the actual tree has $7$ leaves plus $3$ internal nodes (root, the a-branch node, the na-branch node… plus the deeper ana branch) — count them in the figure. Nodes $=7+4=11$? Let's count precisely: leaves $\{0,1,2,3,4,5,6\}$ = 7; internal nodes = root, node after a , node after ana, node after na = 4. Total $=11$, edges $=11-1===10==$, comfortably $\le 2n=12$. ✔