Suffix tree (conceptual): Worked examples — Hinglish deep dive

3.8.8 · D3 · Coding › String Algorithms › Suffix tree (conceptual)

Yeh page Suffix tree (conceptual) ki "apne haath se try karo" companion hai. Hum har tarah ke questions cover karenge jo ek suffix tree face kar sakta hai — ek normal substring search se lekar weird degenerate cases tak (empty pattern, single repeated letter, pattern jo ek edge ke andar khatam hota hai) — aur har ek ko poori tarah solve karenge.

Definition Do words jo hum baar baar use karenge

Terminal $. Koi bhi suffix tree banane se pehle hum ek unique end-marker $ (ek symbol jo alphabet mein nahi hai) append karte hain, toh hum hamesha $S\$$ ke saath kaam karte hain. **Kyun?** Iske bina ek chhota suffix (jaise `a`) ek lambe suffix ka *prefix* ban sakta tha (jaise `ana`) aur ek edge ke andar *khatam* hota edge ke bajay apne leaf par. `$ ` har suffix ko uska apna leaf deta hai — exactly $n + 1$ .
Root-string of a node. Root se neeche ek node tak jao aur saare edge labels concatenate karo jo tumne cross kiye. Woh resulting string us node ki root-string hai. Example: us node ki root-string jahan pahunchne ke liye edge a phir edge na se gaye, ana hai. Root se jo bhi string spell kar sako woh exactly kisi node ki root-string hai (ya kisi edge ke label ka prefix).

Scenario matrix

Suffix tree ka har question in case classes mein se kisi ek mein aata hai. Hamara kaam har row ko cover karna hai.

#	Case class	Kya tricky banata hai	Covered by
A	Pattern present, ek node par khatam hota hai	clean walk, branching point par stop	Ex 1
B	Pattern present, ek edge ke andar khatam hota hai	tum mid-label rukते ho, node par nahi	Ex 2, Ex 2b
C	Pattern absent — mid-edge mismatch	compressed edge ke andar galat letter	Ex 3
D	Pattern absent — node par koi matching edge nahi	koi bhi child agli letter se shuru nahi hota	Ex 3
E	Occurrences count karna (leaves below)	subtree leaves count karni hain, stop point nahi	Ex 4
F	Degenerate: empty pattern / single char	zero-length, whole-alphabet answers	Ex 5
G	Degenerate: all-same string `aaaa$`	maximal sharing, deepest-chain repeats	Ex 6
H	Limiting: longest repeated substring	char depth se deepest internal node	Ex 7
I	Real-world word problem	DNA / log search framing	Ex 8
J	Exam twist: kyun `$` leaf count badalta hai	reasoning, walking nahi	Ex 9

Yeh woh tree hai jo hum banana$ ke liye padhenge. Examples se pehle isse dhyan se dekho — neeche sab kuch isi picture ko "dekhta" hai.

Ex 1 — Case A: pattern present, node par khatam hota hai

Worked example Kya

ana, banana ki substring hai? Walk kahan rukti hai? Forecast: abhi guess karo — kya walk ek node par khatam hoti hai ya ek edge ke andar, aur ana kitni baar aata hai?

Step 1. Root par shuru karo. $P$ ka agla letter a hai. Woh child edge dhundho jo a se shuru hoti hai. Yeh step kyun? Rule 4 ke anusaar (node se nikalne wali edges distinct characters se shuru hoti hain), zyada se zyada ek edge match kar sakti hai — walk deterministic hai.

Step 2. Woh edge a se labeled hai. Consume karo → ab hum us internal node par hain jo a se reach hota hai. Pattern remaining: na. Yeh step kyun? Hum pattern letters ko edge letters ke against kharchte hain, ek region at a time.

Step 3. Us node se, agla letter n hai. n se shuru hone wali edge lo, labeled na. na consume karo. Pattern ab empty hai aur hum exactly ek internal node par land karte hain. Yeh step kyun? Jab pattern khatam ho jaata hai aur hum ek node par baithe hain, $P$ match hua aur hum ek branch point par ruke (case A).

Answer: ana hai ek substring; walk us internal node par khatam hoti hai jiska root-string (root se concatenated edge labels) ana hai.

Verify: banana aankhon se scan karo — b·ana·na index 1 par aur ban·ana index 3 par. ana indices 1 aur 3 par aata hai, aur node ana ke neeche exactly 2 leaves hain (indices 1 aur 3). Match. ✓

Ex 2 — Case B: pattern present, ek edge के andar khatam hota hai

Worked example Kya

nan, banana ki substring hai? Walk exactly kahan rukti hai? Forecast: letters nan — kya tum ek node par finish karte ho ya ek edge ke beech mein?

Step 1. Root se, agla letter n. n se shuru hone wali edge lo; uska label na hai. n consume karo, phir a. Pattern remaining: n. Ab hum us internal node par hain jo na se reach hota hai. Yeh step kyun? Hum compressed label ko character-by-character match karte hain.

Step 2. Node na se, agla pattern letter n hai. n se shuru hone wali child edge labeled na hai (jo nana$ leaf tak jaati hai). Us edge ka pehla letter n match karo — pattern ab empty hai, lekin hum edge के andar hain, ek character andar. Yeh step kyun? Pattern agla node pahunchne se pehle khatam ho gaya. Yeh bilkul valid hai: hum ek mid-edge position par hain.

Answer: nan hai ek substring; walk na edge के andar rukti hai apne pehle n ke baad.

Verify: ba·nan·a — nan index 2 par hai. Ek occurrence. Rukne wali edge neeche ek single leaf (index 2) tak jaati hai, ek occurrence ke consistent. ✓

Ex 2b — Case B bilkul pehli edge par (sabse simple mid-edge match)

Worked example Kya

b, banana ki substring hai? Walk kahan rukti hai? Forecast: kya single letter b ek node par land karta hai ya ek edge ke andar? (Yeh root par canonical Case B hai.)

Step 1. Root se, $P$ ka agla (aur single) letter b hai. Rule 4 ke anusaar, exactly ek edge b se shuru ho sakti hai: woh edge labeled banana$. Yeh step kyun? b ek suffix ke liye unique hai, toh root ke paas sirf ek b-edge hai — deterministic.

Step 2. Us edge ke pehle character b ko match karo. Pattern ab empty hai, lekin hum us edge mein sirf ek character andar hain — uske child node ke paas kahin nahi. Yeh step kyun? Yahan tak ki pehli edge par, ek chhota pattern mid-label khatam hota hai. Yeh sabse simple possible mid-edge stop hai.

Answer: b hai ek substring; walk root edge banana$ के andar rukti hai apne pehle character ke baad. Neeche ek leaf (index 0) → ek baar aata hai.

Verify: banana — b sirf index 0 par hai → 1 occurrence ✓, rukne wali edge ke neeche single leaf ke saath match karta hai.

Ex 3 — Cases C & D: absent hone ke do tarike

Worked example Kya

nax aur bx, banana ki substrings hain? Forecast: har ek ke liye, kya tum fail karoge kyunki ek node par koi child edge exist nahi karti (Case D), ya kyunki ek compressed edge ke andar ek letter disagree karta hai (Case C)?

Part (i) — nax → Case D (node par koi matching child nahi). Step 1. n, a ko na edge se node na tak match karo (jaise Ex 2 mein). Hum cleanly ek node par pahunchte hain. Step 2. Agla letter x. Node na se, children n (edge na) aur $ se shuru hote hain. Koi bhi x se shuru nahi hota. Yeh step kyun? Hum ek node par khade hain aur koi bhi child edge required character se shuru nahi hoti → walk continue nahi ho sakti. Failure ek node par = Case D. Answer (i): nax substring NAHI hai — Case D (node par koi matching child nahi).

Part (ii) — bx → Case C (strictly ek compressed edge ke andar mismatch). Step 1. Root se, letter b edge labeled banana$ select karta hai (b ek suffix ke liye unique hai). Step 2. b consume karo (us edge ke andar position 1). Agla pattern letter x hai, lekin edge ka agla stored character a hai. x ≠ a. Yeh step kyun? Ek compressed label के andar mismatch match ko immediately khatam kar deta hai — tum kabhi node tak nahi pahuncho. Failure mid-edge = Case C. Answer (ii): bx substring NAHI hai — Case C (mismatch mid-edge).

Verify: banana mein bilkul koi x nahi hai, toh dono fail hone chahiye. ✓ Dono failures alag hain kahan: nax ek node par khada fail karta hai (D), bx ek edge ke beech mein fail karta hai (C).

Ex 4 — Case E: occurrences count karna

Worked example

a, banana mein kitni baar aata hai? Aur na? Forecast: padhne se pehle dono counts guess karo.

Step 1 — a match karo. Root se a labeled edge lo; uska single character consume karo. Pattern a exactly us waqt khatam hota hai jab hum internal node a par pahunchte hain — yeh ek clean Case-A stop on a node hai, mid-edge position nahi. Yeh step kyun? Depth $∣ P ∣$ tak pahunchne ka matlab hai $P$ match hua; yahan label a length 1 hai, toh match point exactly node par land karta hai. Count ab neeche subtree mein rehta hai.

Step 2 — subtree mein leaves count karo. Node a ke neeche suffixes a(5), ana(3), anana(1) ke leaves hain. Yeh 3 leaves hain. Yeh step kyun? Stop point ke neeche har leaf = ek suffix jo $P$ se shuru hota hai = $P$ ka ek occurrence. Answer: a 3 baar aata hai.

Step 3 — na match karo. Root se na edge lo, dono characters consume karo; pattern exactly internal node na par khatam hota hai. Uske neeche: na(4) aur nana(2) ke leaves → 2 leaves. Answer: na 2 baar aata hai.

Verify: b a n a n a — letter a indices 1, 3, 5 par hai → 3 baar ✓. na indices 2, 4 par → 2 baar ✓. Counting formula = match ke neeche leaves. ✓

Ex 5 — Case F: degenerate patterns (empty aur single char)

Worked example

$P =$ "" (empty) aur $P =$ z (ek letter jo $S$ mein nahi hai) ke liye tree kya jawab deta hai? Forecast: empty string ke kitne occurrences? Ek missing letter ke?

Step 1 — empty pattern. Zero letters match karne ke saath, hum root nahi chodते. Hum depth 0 par "tree mein" hain. Yeh step kyun? Walk $∣ P ∣ = 0$ characters consume karti hai, toh yeh root par trivially succeed hoti hai. Occurrences: root ke neeche saare leaves count karo = har suffix = == $n + 1 = 7$ == positions. Empty string har character se pehle hai, $n + 1$ = 7 saari jagahon par (indices 0..6 $-only suffix including).

Step 2 — missing letter z. Root se, koi bhi child edge z se shuru nahi hoti. Yeh step kyun? Bilkul pehle step par failure (root par Case D). Answer: z 0 baar aata hai — substring nahi.

Verify: empty string 7 saare suffixes ka prefix hai → 7 leaves ✓. z ∉ banana$ → 0 ✓.

Ex 6 — Case G: all-same string `aaaa`

Worked example

$S =$ aaaa ke liye suffix tree ki shape banao aur aa ke occurrences count karo. Tree mein kitne internal nodes hain? Forecast: kitne internal nodes? aa kitni baar aata hai?

Step 0 — terminal append karo. Jaise humari opening definition mein bataya, ek proper suffix tree $S\$$ par banaya jaata hai, toh hum$ S$ = $‘ aaaa$ ke saath kaam karte hain. Yahan $n = |S| = 4$. *Yeh step kyun?* $‘ k e bina, ha r c hh o t aa l l - ‘ a ‘ s u f f i x e k l amb e m e in c hh u pt a; ‘$ ` har ek ko uska apna leaf force karta hai.

Step 1 — aaaa$ ke suffixes list karo: aaaa$, aaa$, aa$, a$, $ (5 suffixes, indices 0–4, toh $n + 1 = 5$ leaves). Yeh step kyun? Suffixes raw material hain; maximal sharing ka matlab hai maximal compression stress-test.

Step 2 — har non-$ suffix a se shuru hota hai. Toh root se ek shared chain hai jo branch karti hai har baar jab ek $ wahan peel off ho sakta hai. Internal (branching) nodes exactly root-strings a, aa, aaa hain — har ek par, ya toh ek $ yahan terminate karta hai ya ek aur a continue karta hai, giving ≥ 2 children. Yeh step kyun? Branching exactly wahan hoti hai jahan suffixes agree karna band karte hain — yahan har extra a ek branch point hai kyunki ek suffix terminate kar sakta hai ($) jabki doosre ek aur a ke saath continue karte hain. Internal-node count: branching nodes a, aa, aaa hain ⇒ 3 internal nodes (root unhe count nahi kiya jaata). Yeh $n = 4$ ke liye bound "≤ $n - 1$ non-root internal nodes" se match karta hai.

Step 3 — aa count karo. Root se a, a match karo, exactly node aa par khatam karo. Uske neeche woh suffixes hain jo aa se shuru hote hain: aa$(2), aaa$(1), aaaa$(0) → 3 leaves. Answer: aa 3 baar aata hai; tree mein 3 internal nodes ka spine hai (a, aa, aaa) plus 5 leaves.

Verify: aaaa mein, aa indices 0,1,2 par hai → 3 occurrences ✓. Leaves $= n + 1 = 5$ ✓; internal branching nodes $= 3$ ✓. Yeh maximal-repeat extreme hai; note karo $ hi hai jo ise ek infinite edge mein collapse hone se rokta hai.

Ex 7 — Case H: longest repeated substring (limiting query)

Worked example

banana ka longest repeated substring dhundho. Forecast: kaunsi string repeat karti hai aur jitni ho sake utni lambi hai?

Step 1 — repeated ⇒ branching internal node. Ek substring $\geq 2$ baar repeat karti hai iff uski root-string ek internal (branching) node par khatam hoti hai — kyunki uske neeche $\geq 2$ leaves hain. Yeh step kyun? Rule 2 ke anusaar, ek internal node ke $\geq 2$ children hain ⇒ $\geq 2$ different continuations ⇒ $\geq 2$ occurrences.

Step 2 — longest ⇒ character depth se deepest. Internal nodes mein, character depth (total root-string length root→node) compute karo:

node a → depth 1
node na → depth 2
node ana → depth 3 ← deepest

Yeh step kyun? Hum zyada se zyada letters chahte hain, toh hum character depth maximize karte hain (node count nahi). Answer: longest repeated substring = ==ana==, length 3, indices 1 aur 3 par hota hai.

Verify: banana — ana index 1 par (b**ana**na) aur index 3 par (ban**ana**) → repeat karta hai ✓. Koi bhi length-4 substring repeat nahi karti (check karo anan sirf index 1 par aata hai). ✓

Ex 8 — Case I: real-world word problem

Worked example Ek DNA scanner read

$S =$ ACGTACG ko ek suffix tree mein store karta hai. Ek lab poochti hai: "kya motif GTA appear karta hai, aur ACG kitni baar appear karta hai?" Forecast: dono answers guess karo.

Step 1 — motif GTA. Root se walk karo: G → T → A. Har step ko ek matching edge/character milna chahiye. Yeh step kyun? Substring query = walk; cost $O (∣ P ∣) = O (3)$ , read length $n = 7$ se independent. ACGTACG padhne par: AC**GTA**CG — GTA index 3 par hai. Walk succeed hoti hai. GTA present hai.

Step 2 — ACG count karo. A,C,G match karo phir neeche leaves count karo. ACG se shuru hone wale suffixes: ACGTACG(0) aur ACG(4) → 2 leaves. Yeh step kyun? Occurrences = match point ke neeche leaves. Answer: ACG 2 baar aata hai (indices 0 aur 4 par).

Verify: ACGTACG — ACG index 0 par (**ACG**TACG) aur index 4 par (ACGT**ACG**) → 2 ✓. GTA index 3 par → present ✓. Units check: answer ek count hai (dimensionless), aur $2 \leq n = 7$ suffixes. ✓

Ex 9 — Case J: exam twist (reason karo, walk mat karo)

Worked example Koi

abab ka tree $ ke bina banata hai. Uske kitne leaves hain, aur kya toot ta hai? Forecast: kya 4 leaves hone chahiye? Ya kam?

Step 1 — abab ke suffixes list karo (yahan $n = ∣ S ∣ = 4$ ): abab, bab, ab, b (indices 0–3). Yeh step kyun? Hum rule "har suffix ke liye ek leaf" ko self-nested case ke against test karte hain.

Step 2 — nesting pakdo. ab, abab ka ek prefix hai; b, bab ka prefix hai. Toh suffix ab abab spell karne wali edge ke andar khatam hota hai, aur b, bab ke andar — unhe apne leaves nahi milते. Yeh step kyun? Ek unique terminator ke bina, ek chhota suffix ek lambe ke andar chhupta ja sakta hai, "har suffix apne leaf par" violate karta hai.

Step 3 — $ add karo → abab$. Ab suffixes hain abab$, bab$, ab$, b$, $ (5 hain). $ unique hai, toh koi suffix doosre ka prefix nahi; har ek apne leaf par khatam hota hai → exactly $n + 1 = 5$ leaves. Answer: $ ke bina, abab 4 true leaves se kam deta hai (2 suffixes edges ke andar chhupta hai); $ ke saath, abab$ exactly 5 leaves deta hai.

Verify: abab ke liye $n = 4$ ; $ ke saath, leaves $= n + 1 = 5$ ✓. Yahi precisely isliye hai ki parent note terminal symbol par insist karta hai.

Recall Matrix par self-test

Har ek kaunsa case class hit karta hai? nan in banana ::: Case B — present, edge ke andar khatam hota hai. b in banana ::: Case B — present, bilkul pehli (root) edge ke andar khatam hota hai. bx in banana ::: Case C — strictly ek compressed edge ke andar mismatch. nax in banana ::: Case D — ek node par khade hue koi matching child nahi. Length- $n$ string mein empty string ke occurrences ::: Case F — degenerate, answer $n + 1$ . banana ka longest repeated substring ::: Case H — ana, deepest internal node, depth 3. abab$ ke tree ke leaves ::: Case J — exactly 5 ( $n + 1$ ). $n$ kya hai? ::: Original string $S$ ki length ($ append karne se pehle).

Connections

Suffix tree (conceptual) — woh parent concept jin par yeh examples practice hain.
Trie — jahan se uncompressed walk logic aati hai.
Suffix Array — same queries kam memory ke saath; occurrences ek range ban jaate hain.
Ukkonen's Algorithm — humne jis tree ko padha woh $O (n)$ mein kaise banta hai.
Longest Common Substring — Ex 7 ko do strings tak extend karta hai.