eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1.5 секунда
Лимит использования памяти 256 MiB

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

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

Входные данные

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

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

Выходные данные

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

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

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

Пример

Входные данные #1
ab$
ac#
Выходные данные #1
8
0 1 2 3
0 0 2 3
0 0 0 1
3 0 1 3
3 1 1 3
0 0 1 3
0 1 1 3
Входные данные #2
aba$
baab#
Выходные данные #2
14
0 1 4 5
0 0 3 4
0 0 0 1
3 0 3 4
3 1 2 5
3 0 1 2
6 1 4 5
6 0 2 4
0 0 1 2
9 1 4 5
9 0 2 3
11 0 3 4
11 1 2 5

Примечание

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

Источник Зимняя школа Харьков 2013, День 6 - Г.Агапова и И.Фефера