İki sətirin suffiks ağacı
Verilmiş s və t sətirlərini nəzərə alaraq, bu sətirlərin bütün sonluqlarını əhatə edən sıxılmış sonluq ağacı qurun.
Bu ağacın zirvələrinin sayını minimuma endirin.
Giriş verilənləri
Birinci sətirdə s sətiri verilib (1 ≤ |s| ≤ 10^4), sətirin son simvolu "$"-dir, qalan simvollar isə kiçik latın hərfləridir. İkinci sətirdə t sətiri verilib (1 ≤ |t| ≤ 10^4), sətirin son simvolu "#"-dir, qalan 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ə nömrələyin, zirvədən çıxan kənarların leksik qrafik sıralama qaydasında alt ağacları keçərək. Simvolların sırasını təyin etmək üçün ASCII kodlarından istifadə edin.
Birinci sətirdə ağacın zirvələrinin sayı olan n tam ədədini çıxarın. Sonrakı n-1 sətirdə zirvələrin nömrələrinin artma qaydasında, kök zirvəsi istisna olmaqla, ağacın zirvələrinin təsvirini çıxarın.
Ağacın v zirvəsinin təsviri dörd tam ədəddən ibarətdir: p, w, lf, rg, burada p (0 ≤ p < n, p ≠ v) — cari zirvənin valideyninin nömrəsi, w (0 ≤ w ≤ 1) — kənardakı alt sətiri təyin etmək üçün sətirin nömrəsi. Əgər w=0, onda p-dən v-yə gedən kənarda s[lf...rg-1] alt sətiri yazılıb (0 ≤ lf < rg ≤ |s|). Əgər w=1, onda p-dən v-yə gedən kənarda t[lf...rg-1] alt sətiri yazılıb (0 ≤ lf < rg ≤ |t|).