Суфіксне дерево двох рядків
Дано рядки 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|).