Sufiks ağacı
Verilmiş s sırası üçün sıxılmış sufiks ağacı qurun və onu təsvir edin.
Minimum sayda zirvə ehtiva edən belə bir ağac tapın.
Giriş verilənləri
Birinci sətirdə s sırası (1 ≤ |s| ≤ 10^5) verilir. Sıra son simvolu dollar işarəsi "$" ilə bitir, digər simvollar isə kiçik latın hərfləridir.
Çıxış verilənləri
Ağacın zirvələrini 0-dan n-1-ə qədər dərinlik üzrə keçmə qaydasında, zirvədən çıxan kənarları leksikografik sıralama qaydasında nömrələyin. Simvolların sırasını müəyyən etmək üçün ASCII kodlarından istifadə edin.
Birinci sətirdə ağacın zirvələrinin sayı olan tam ədəd n verin. Sonrakı n-1 sətirdə kök xaricindəki ağacın zirvələrinin təsvirini onların nömrələrinin artma qaydasında verin.
Ağacın v zirvəsinin təsviri üç tam ədəddən ibarətdir: p, lf, rg, burada p (0 ≤ p < n, p ≠ v) — cari zirvənin əcdadının nömrəsidir. p-dən v-yə aparan kənarda s[lf...rg-1] (0 ≤ lf < rg ≤ |s|) alt sırası yazılıb.
Qeyd
Alt sırası s[l...r] (0 ≤ l ≤ r < |s|) s = s_0s_1...s_{|s|-1} sırası (burada |s| — s sıranın uzunluğudur) s_ls_{l+1}...s_r sırası adlanır.