Exercises — Suffix tree (conceptual)

Baar baar aage ka letter kaato, $ ko tail par rakhte hue:

Yeh $n+1=7$ suffixes hain. 7 kyun, 6 kyun nahi? akela $ khud ek suffix hai.

Exactly ==$n+1=7$== leaves — har suffix ke liye ek. $ guarantee karta hai ki koi suffix doosre ka prefix nahi hoga, isliye har suffix apne khud ke leaf par khatam hota hai, kisi edge ke beech mein rukne ki bajay.

True. Sirf ek child wala node koi decision nahi leta — compression ke dauran yeh ek single edge mein absorb ho jaata hai. Isliye har surviving internal node ek branching point hota hai jisme $\ge 2$ children hote hain.

Root se shuru karo. Pehla edge jiska label n se shuru ho woh na label wala hai. Usse chalo:

• n match ✔, a match ✔ — ab hum na ke baad wale branching node par hain.
• $P$ ka agla character n hai. Us node se ek outgoing edge n se shuru hoti hai (na$ edge). n match ✔.

Humne poora nan spell kar diya. Haan, nan ek substring hai. Cost $=|P|=3$ character-steps.

a → n → a walk karo. Yeh tumhe exactly us branching node par le jaata hai jiska root-path ana hai (figure mein yellow node dekho). Ab uske subtree mein leaves count karo. ana ke neeche do leaves hain: ek na$ continue karti hai (leaf 1, suffix anana$) aur ek $ continue karti hai (leaf 3, suffix ana$). Toh ana 2 baar aata hai — start indices $1$ aur $3$ par. Check: b(anana) → positions 1 aur 3, aur sach mein banana = b an an a, ana index 1 par (anana) aur index 3 par (ana) hai. ✔

n,a,n,a,$ walk karo. Tum ek leaf par khatam hote ho, leaf number $2$ — kyunki poora suffix nana$ index $2$ par start hota hai. Leaf tak pahunchna (edge ke beech mein rukne ki jagay) matlab yeh hai ki tumne ek poora suffix spell kar diya.

String-depth se measure karke deepest internal (branching) node dhundho. Branching matlab $\ge 2$ alag continuations exist hain, isliye uski root-path string $\ge 2$ baar aati hai. Hamare tree mein deepest branching node ki string-depth 3 hai, jo ana spell karta hai. Isliye longest repeated substring ana hai (yeh indices 1 aur 3 par aata hai, overlap karte hue). Length $=3$.

$L$ leaves wale rooted tree mein jisme har internal node mein $\ge 2$ children hain, internal nodes $\le L-1$ hote hain. Yahan $L=n+1$, toh internal nodes $\le n$. Total nodes $\le (n+1)+n===2n+1===O(n)$. $\ge 2$-children rule kyun matter karta hai: agar single-child chains bachti, toh count badh jaata. Compression yeh rule enforce karta hai, tree ko linear size par cap karta hai.

Har edge apna label do integers $(i,j)$ ke roop mein store karta hai jiska matlab hai "substring $S[i..j]$" — copied text kabhi nahi. $O(n)$ edges hain (har non-root node ke liye ek), aur $2$ integers per edge, toh storage $O(n)$ words hai. Conceptual label lamba ho sakta hai (jaise nana$), lekin hum sirf $S$ mein do endpoints rakhte hain.

Rule 4: ek node se koi bhi do edges ek hi character se shuru nahi ho sakti. banana$ ke suffixes mein distinct first characters hain b, a, n, $. Toh root ke exactly 4 children hain:

• banana$ → leaf 0 (starts with b, unique, toh leaf tak ek lamba edge).
• a… → branching node (suffixes anana$, ana$, a$ sabhi a se start hote hain).
• na… → branching node (nana$, na$).
• $ → leaf 6.

Suffixes: aaaa$(0), aaa$(1), aa$(2), a$(3), $(4) → $n+1=5$ leaves. Longest repeated substring: deepest branching node. String aaa indices 0 aur 1 par aata hai (do baar), aur aaaa ek baar aata hai. Toh longest repeat aaa hai, length $3=n-1$. ($k$ identical letters ki run ke liye, longest repeat woh run minus ek letter hai.)

Algorithm: root se start karo, current position = $P$ ki beginning. Baar baar: woh outgoing edge choose karo jiske label ka first character $P$ ke current character ke barabar ho (rule 4 ke hisaab se zyaada se zyaada ek hogi); us edge par chalte hue character-by-character compare karo. Agar koi comparison fail ho, ya tum edge ke end par aa jao aur koi matching next edge nahi mili, no jawab do. Agar tum $P$ ke saare characters consume kar lo (chahe tum edge ke beech mein ruko ya node par), yes jawab do. Cost: $P$ ka har character zyaada se zyaada ek baar padha jaata hai → $O(|P|)$, $n$ se independent. Edge case jo naive testers ko tod deta hai: ek edge ke andar rukna. nan ek edge ke middle mein khatam hota hai lekin phir bhi ek valid substring hai. Ek tester jo sirf "yes" tab kahe jab woh exactly ek node par utre, woh nan ko galat reject kar dega. Fix: "yes" jab bhi $P$ poori consume ho jaaye, node ya mid-edge.

Haan, overlaps count hote hain. Count = match ke neeche leaves ki sankhya = un suffixes ki sankhya jo $P$ se start hote hain. Suffix anana$ (index 1) aur suffix ana$ (index 3) dono ana se start hote hain, toh dono leaves count hoti hain — chahe spans $S$ mein overlap karti hon ya nahi. Tree starting positions count karta hai, aur overlapping matches ke alag starting positions hote hain. ana ka answer: 2.

• KMP Algorithm: ek pattern, ek text, ek baar scan — $O(n+|P|)$, tiny memory. Tab use karo jab tum ek known text ek baar search karo.
• Suffix Array: suffix tree jaisi hi substring power lekin fraction of memory; search $O(|P|\log n)$ hai. Tab use karo jab text fixed ho aur kaafi baar query ho aur memory matter kare.
• Suffix tree: richest structure — $O(|P|)$ search, longest-repeat, Longest Common Substring generalized tree se — lekin heaviest memory (bada constant). Tab use karo jab tumhe woh advanced queries chahiye aur space afford kar sako.

Kisi bhi rooted tree mein, #edges $=$ #nodes $-1$. Humne prove kiya ki total nodes $\le 2n+1$, toh edges $\le 2n$. banana$ ke liye ($n=6$): actual tree mein $7$ leaves hain plus $3$ internal nodes (root, a-branch node, na-branch node… plus deeper ana branch) — figure mein unhe count karo. Nodes $=7+4=11$? Precisely count karte hain: leaves $\{0,1,2,3,4,5,6\}$ = 7; internal nodes = root, a ke baad wala node, ana ke baad wala node, na ke baad wala node = 4. Total $=11$, edges $=11-1===10==$, comfortably $\le 2n=12$. ✔