Suffix tree (conceptual) — Hinglish notes

3.8.8 · Coding › String Algorithms

YEH cheez EXIST kyun karti hai?

Lo $S =$ banana. Iske suffixes hain:

start index	suffix
0	banana
1	anana
2	nana
3	ana
4	na
5	a

Inki trie mein ek root-to-leaf path hota hai har suffix ke liye. Problem yeh hai: isme $O (n^{2})$ nodes aa sakte hain. Isko hum compression se fix karte hain.

Suffix tree EXACTLY kya hoti hai?

Idea KAISE build karte hain (trie se derivation)

Isse KYA kar sakte hain (80/20 payoff)

Recall Feynman: 12-saal ke bachche ko samjhao

Soch ke ek lambi word likhte ho aur tum chahte ho uske andar chhupi har chhoti piece ka ek magic map. Tum us word ko lete ho aur baar baar aage ka ek letter kaatte jaate ho — banana, anana, nana, … — aur in saari tails ko ek aisi tree mein daal do jahan same se shuru hone wale words ek hi branch share karein. Ab agar koi dost puchhe "kya nan isme hai?", tum bas walk karo: n → a → n, aur agar path complete ho jaata hai, toh haan woh andar hai! Neeche kitne leaf-tags latak rahe hain ginne se pata chalta hai woh kitni baar aata hai. $ end mein ek chhoti si flag hai jo ensure karti hai har tail ko apna leaf mile, taaki koi cheez doosre ke andar na chhup jaaye.

Active Recall

A suffix tree is a compressed trie of what?

String

S\$$ ke saare suffixes ka. Why append a unique terminal `

? ::: Taaki koi suffix doosre ka prefix na ho; har suffix phir apne leaf par khatam hota hai, exactly $n+1$ leaves guaranteed hoti hain. How many leaves does a suffix tree of $S\$ have? ::: Exactly $n+1$ (ek har suffix ke liye,

‘ s u f f i x bhiin c l u d e hai) . C o n s t r ain t o nin t er na l n o d es (b es i d esr oo t)? ::: H a r e k k e k am se k am 2 c hi l d r e nh o t e hain (y e hb r an c hin g p o in t s hain) . W h y i s t o t a l s p a ce

O(n)

an d n o t

O(n^2)

? ::: E d g e l ab e l s

m e inin d e x p ai r s

(i,j)

k e f or mm e in s t or e h o t ihain, co p i e d s u b s t r in g s nahi;

O(n)

e d g es k es aa t h w o h

O(n)

s p a ce hai . T im e t o t es t i f p a tt er n

i s a s u b s t r in g ? :::

O(\lvert P\rvert)

— ba s

k ec ha r a c t er s ma t c hk a r t e h u e n eec h e w a l k k a r o . H o w d oy o u co u n t occ u r r e n ceso f

a f t er ma t c hin g i t ? ::: M a t c h p o in t k e n eec h es u b t r ee m e in l e a v es k i co u n t k a r o . W ha t d oes t h e d ee p es t in t er na l n o d e (b y c ha r d e pt h) g i v ey o u ? :::

k a l o n g es t r e p e a t e d s u b s t r in g . W h y m u s t e d g eso u t o f an o d es t a r tw i t h d i s t in c t c ha r a c t er s ? ::: T aak i p a tt er nma t c hk a r na d e t er mini s t i c h o — ha r n e x t c ha r a c t er k e l i y e m os t e k hi e d g e f o l l o w k a r nih o . S u b s t r in g o f

e q u a l s a p r e f i x o f w ha t ? :::

S$ ke kisi suffix ka prefix — isliye suffixes ki tree substring queries answer karti hai.

Connections

Trie — suffix tree ka uncompressed ancestor.
Suffix Array — same info, kam memory; practice mein aksar prefer kiya jaata hai.
Ukkonen's Algorithm — linear-time online construction.
KMP Algorithm — alternative single-pattern matcher, $O (n + m)$ .
Longest Common Substring — do strings ki generalized suffix tree se solve hota hai.
Burrows-Wheeler Transform — compression mein use hone wala related suffix-structure.

Task	Time
Build (Ukkonen)	$O (n)$
Kya $P$ ek substring hai?	$O (∣ P ∣)$
$P$ ki occurrences count karo	$O (∣ P ∣ + occ)$
Longest repeated substring	$O (n)$

YEH cheez EXIST kyun karti hai?

Suffix tree EXACTLY kya hoti hai?

Idea KAISE build karte hain (trie se derivation)

Isse KYA kar sakte hain (80/20 payoff)

Active Recall

Connections

Concept Map