Суффиксное дерево двух строк
Даны строки s и t. Постройте сжатое суффиксное дерево, которое содержит все суффиксы строки s и строки t.
Найдите такое дерево, которое содержит минимальное количество вершин.
Входные данные
В первой строке записана строка s (1 ≤ |s| ≤ 10^4), последний символ строки равен "$", остальные символы строки маленькие латинские буквы. Во второй строке записана строка t (1 ≤ |t| ≤ 10^4), последний символ строки равен "#", остальные символы строки маленькие латинские буквы.
Выходные данные
Пронумеруйте вершины дерева от 0 до n-1 в порядке обхода в глубину, обходя поддеревья в порядке лексикографической сортировки исходящих из вершины ребер. Используйте ASCII-коды символов для определения их порядка.
В первой строке выведите целое число n — количество вершин дерева. В следующих n-1 строках выведите описание вершин дерева, кроме корня, в порядке увеличения их номеров.
Описание вершины дерева v состоит из четырех целых чисел: p, w, lf, rg, где p (0 ≤ p < n, p ≠ v) — номер родителя текущей вершины, w (0 ≤ w ≤ 1) — номер строки для определения подстроки на ребре. Если w=0, то на ребре, ведущем из p в v, написана подстрока s[lf...rg-1] (0 ≤ lf < rg ≤ |s|). Если w=1, то на ребре, ведущем из p в v, написана подстрока t[lf...rg-1] (0 ≤ lf < rg ≤ |t|).