İki sıra üçün sufiks ağacı
Verilmiş s və t sətirlərinin bütün sonluqlarını əhatə edən sıxılmış sonluq ağacı qurun.
Bu ağacın mümkün olan ən az sayda zirvəyə malik olmasını təmin edin.
Giriş verilənləri
Birinci sətirdə s sətiri verilir (1 ≤ |s| ≤ 10^5), burada sətirin son simvolu "$"-dir, digər simvollar isə kiçik latın hərfləridir.
İkinci sətirdə t sətiri verilir (1 ≤ |t| ≤ 10^5), burada sətirin son simvolu "#"-dir, 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ın leksikoqrafik 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ə n tam ədədini çıxarın — ağacın zirvələrinin sayı. Sonrakı n-1 sətirdə, kök istisna olmaqla, ağacın zirvələrinin təsvirlərini onların nömrələrinin artma qaydasında verin.
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 əcdadının nömrəsi, w (0 ≤ w ≤ 1) — kənardakı alt sətiri müəyyən etmək üçün sətirin nömrəsi. Əgər w = 0 olarsa, p-dən v-yə gedən kənarda s[lf...rg-1] alt sətiri yazılmışdır (0 ≤ lf < rg ≤ |s|). Əgər w = 1 olarsa, p-dən v-yə gedən kənarda t[lf...rg-1] alt sətiri yazılmışdır (0 ≤ lf < rg ≤ |t|).
Qeyd
Alt sətir s[l...r] (0 ≤ l ≤ r < |s|) sətiri s = s_0s_1...s_{|s|-1} (burada |s| — s sətirinin uzunluğu) sətirinin s_ls_{l+1}...s_r sətiridir.