eolymp
bolt
Try our new interface for solving problems
Məsələlər

Суффиксное дерево

Суффиксное дерево

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Дана строка s. Постройте сжатое суффиксное дерево для строки s и выведите его.

Найдите такое дерево, которое содержит минимальное количество вершин.

Giriş verilənləri

В первой строке записана строка s (1|s|10^5), последний символ строки доллар "$", остальные символы строки маленькие латинские буквы.

Çıxış verilənləri

Пронумеруйте вершины дерева от 0 до n-1 в порядке обхода в глубину, обходя поддеревья в порядке лексикографической сортировки исходящих из вершины ребер. Используйте ASCII-коды символов для определения их порядка.

В первой строке выведите целое число n — количество вершин дерева. В следующих n-1 строках выведите описание вершин дерева, кроме корня, в порядке увеличения их номеров.

Описание вершины дерева v состоит из трех целых чисел: p, lf, rg, где p (0p < n, pv) — номер родителя текущей вершины. На ребре, ведущем из p в v, написана подстрока s[lf...rg-1] (0lf < rg|s|).

Nümunə

Giriş verilənləri #1
aaa$
Çıxış verilənləri #1
7
0 3 4
0 0 1
2 3 4
2 1 2
4 3 4
4 2 4
Giriş verilənləri #2
b$
Çıxış verilənləri #2
3
0 1 2
0 0 2
Giriş verilənləri #3
ababa$
Çıxış verilənləri #3
10
0 5 6
0 0 1
2 5 6
2 1 3
4 5 6
4 3 6
0 1 3
7 5 6
7 3 6

Qeyd

Подстрокойs[l...r] (0lr < |s|) строки s = s_0s_1...s_{|s|-1} (где |s| — длина строки s) называется строка s_ls_{l+1}...s_r.

Mənbə Winter School Kharkov 2013, Day 6 - G.Agapov and I.Fefer