3.8.8 · D1Suffix tree (conceptual)
Ek suffix tree ek aisa single tree hai jo secretly har possible piece (substring) ko ek word ke andar store karta hai, taaki "kya yeh chhota piece andar chhupa hai?" ek short walk se pata chal jaye — upar se neeche. Parent note padhne ke liye sirf ek fact pe trust karna hai — ek substring hamesha kisi tail (suffix) ki shuruaat hoti hai — aur woh thode se symbols samajhne hain jo hum neeche banate hain, ek ek karke.
Yeh page assume karta hai ki aapne kuch nahi dekha. Hum har symbol introduce karte hain, uski picture draw karte hain, aur batate hain ki topic uske bina kyun nahi chal sakta. Upar se neeche padho — har item pichle wale pe lean karta hai.
Ek string bas characters ki ek row hai jo left se right likhi jaati hai, jaise ek wire pe beads.
Poori row ko hum ek single capital letter se name karte hain, usually S S tring ke liye).
Example: S = banana.
Ek row of boxes socho, ek letter per box. Boxes ke neeche addresses printed hain.
Neeche di gayi figure dekho — woh row of boxes hi string S
Topic ko yeh kyun chahiye: poora suffix tree isi ek row S S
i index ek character ka position number hota hai, bilkul 0 se count karte hue left se.
Toh banana mein: b index 0 a index 1
Common mistake Off-by-one trapKyun galat lagta hai: insaan "1, 2, 3…" count karte hain, toh pehla letter lagta hai position 1.
Fix: in algorithms mein hum "0, 1, 2…" count karte hain. Pehla letter index 0
Hum S [ i ] i S [ 3 ] = a.
n Length n S banana ke liye, n = 6 0 , 1 , 2 , … , n − 1 0 5
Ek substring characters ki ek run hai jo S , koi gaps nahi.
Hum S [ i .. j ] i j
Box row ke ek stretch ke around do brackets lagao. Brackets ke beech mein sab kuch, bina koi box skip kiye, ek substring hai. Neeche ki figure mein red bracket S [ 2..4 ] = nan ko highlight karta hai.
Common mistake Substring vs subsequenceKyun confuse hote hain: dono words "sub" se start hote hain.
Fix: ek substring contiguous hota hai (nan from banana — boxes touch karte hain). Ek subsequence boxes skip kar sakta hai (bnn ek subsequence hai lekin substring nahi ). Suffix tree substrings ke baare mein hai — sirf contiguous chunks.
Topic ko yeh kyun chahiye: suffix tree ka poora purpose substrings ke baare mein questions ka jawab dena hai ("kya nan aata hai?"). Yeh woh object hai jo hum dhundhte hain.
Ek prefix ek aisi substring hai jo bilkul shuruaat se start hoti hai (jis bhi word ko hum dekh rahe hain uska index 0 banana ke prefixes: b, ba, ban, bana, banan, banana.
Ek prefix woh hai jo milta hai jab aap word ko right se apne haath se dhako aur jo left mein dikhta hai woh padho. Figure mein sliding hand dekho.
Topic ko yeh kyun chahiye: parent ka key claim — "ek substring kisi suffix ka ek prefix hai" — yeh word use karta hai. Hum suffix aage define karte hain, phir dono ideas ko jodenge.
Ek suffix ek aisi substring hai jo word ke end tak jaati hai.
Tum suffix banate ho front se letters kaatkar.
S = banana ke liye, suffixes yeh "tails" hain:
start index
suffix
0
banana
1
anana
2
nana
3
ana
4
na
5
a
Is baar word ko left se haath se dhako, aur jo right mein bacha woh padho. Haath ki har stopping point ek suffix deti hai. Figure mein haath rightward slide karta hai, chhotay chhotay tails expose karte hue.
Topic ko yeh kyun chahiye: suffix tree literally in sab tails ka tree hai. Exactly n n n
Intuition Sabse important sentenceKoi bhi substring lo — maan lo nan. Yeh kahin beech mein baitha hai. Left slide karo jab tak uski start front-cut ko touch kare: nan tail nana ka front part (prefix) hai (woh suffix jo index 2 har substring kisi tail ki shuruaat hai.
Topic ko yeh kyun chahiye: isliye suffixes ka ek tree substring questions ka jawab de sakta hai. Agar tum sab tails store karo aur unke front-parts walk kar sako, toh koi bhi chunk dhundh sakte ho. Parent note jo kuch bhi karta hai sab is line pe tika hai.
Alphabet allowed characters ka set hai. banana ke liye yeh { a,b,n}
Definition Terminal symbol$
Terminal symbol $ ek special extra character hai jo alphabet mein nahi hota aur sirf ek baar aata hai, bilkul end mein chipka hua: banana$.
Kyun exist karta hai: iske bina, ek tail doosre ka front ho sakti hai (a, ana ka front hai), toh woh tree ke andar khatam ho jaati apni leaf ke bajaye. $ ek unique flag hai jo har tail ko uska apna private ending deta hai.
Ek chhoti flag socho jo last box pe lagi ho. Kyunki koi aur box woh flag nahi rakhta, koi bhi tail accidentally doosri tail ke andar nahi chhup sakti. Neeche tree section ki figure dikhayegi kyun.
Topic ko yeh kyun chahiye: yeh guarantee karta hai "exactly n + 1
Definition Tree vocabulary
Root ::: woh single top box jahan se har walk start hoti hai.Node ::: tree mein koi bhi junction box.Edge ::: do nodes ke beech ek link; suffix tree mein iske upar ek label hota hai (ek substring).Leaf ::: ek bottom node jiske koi children nahi — ek dead end.Internal node ::: ek node jo leaf nahi hai aur root bhi ho sakta hai; ek branching internal node ke ≥ 2 Path ::: root se kisi node tak edges ka trail; uske edge-labels ko order mein padhne se ek string milti hai.
Intuition Ek rule jo walking possible banata haiKisi bhi node se, do edges same character se start nahi hoti . Toh jab tum ek pattern spell kar rahe ho aur agla letter n hai, to zyaada se zyaada ek hi edge ho sakti hai jo tum le sako — walk kabhi ambiguous nahi hoti. Yahi cheez searching ko ek simple, deterministic stroll banati hai.
Topic ko yeh kyun chahiye: "ek path ek substring hai" poori structure ka punchline hai. Tree ek machine hai jahan neeche walk karna = ek substring spell karna .
Definition Index-pair labelEdge pe actual letters likhne ki jagah (jo space waste karta hai), hum do integers store karte hain ( i , j ) S [ i .. j ] S point karte hain copy karne ki jagah.
Common mistake "Labels copy karnaO ( n 2 ) Kyun sahi lagta hai: labels dikhte hain text jaisi (anana$), aur un sab text lengths ko jodna wakai n 2 Fix: hum kabhi copy nahi karte. Do integers per edge × O ( n ) = O ( n )
Topic ko yeh kyun chahiye: yeh trick hi poori wajah hai ki suffix tree O ( n )
O ( f ( n )) zyaada se zyaada f ( n )
O ( n ) linear , sasta.O ( n 2 ) square ki tarah badhti hai — mahenga; input double karo toh kaam chaar guna ho jaata hai.O ( ∣ P ∣ ) ∣ P ∣ n nahi — isliye searching itni fast hai.
Do runners: O ( n ) O ( n 2 )
Topic ko yeh kyun chahiye: parent mein har payoff ("build O ( n ) O ( ∣ P ∣ ) ∣ P ∣ P ∣ ⋅ ∣
String S as a row of boxes
Bridge substring is prefix of a suffix
Tree words root node edge leaf path
Edge label as index pair i j
Isko aise padho: rows of boxes indices aur length deti hain; indices substrings kaatti hain; substrings prefixes aur suffixes mein specialise hoti hain; bridge unhe fuse karta hai; aur tree machinery plus growth ruler milkar finished suffix tree banate hain.
Right side cover karo aur reveal karne se pehle zor se jawab do.
banana mein, S [ 3 ] a (0-based: b=0, a=1, n=2, a=3).
banana ki n 6 0 5
Kya bnn banana ki substring hai? Nahi — yeh boxes skip karta hai, toh yeh subsequence hai, contiguous substring nahi.
banana ki substring S [ 2..4 ] nan.
Length-n Exactly n 0 … n − 1
Bridge complete karo: ek substring kisi ____ ki ____ hoti hai. kisi suffix ki prefix .
End mein $ kyun chipkate hain? Taaki koi bhi tail doosri tail ka front na ho; phir har suffix apni private leaf pe khatam hoti hai.
Edge label ( i , j ) Substring S [ i .. j ]
Tree O ( n ) O ( n 2 ) Edges har ek mein do integers store karti hain, copied text nahi; O ( n ) × = O ( n )
O ( ∣ P ∣ ) Yeh sirf pattern ki length pe depend karta hai, text ke size n
Ek node se, kya do edges same character se start ho sakti hain? Nahi — alag starting characters downward walk ko unambiguous banate hain.
Suffix tree (conceptual) (index 3.8.8) — woh parent jiske liye yeh page tume tayaar karta hai.Trie — woh uncompressed tree jo yeh symbols pehle banate hain.Suffix Array — wohi suffix information ek sorted list ke roop mein stored.Ukkonen's Algorithm — tree actually construct karne ka linear-time tarika.KMP Algorithm — ek aur matcher jo prefixes aur suffixes ki bhi parwah karta hai.Longest Common Substring — in foundations pe bana ek payoff.Burrows-Wheeler Transform — same suffixes use karne wala ek cousin structure. 
