Задачи
Суффиксное дерево
Суффиксное дерево
Постройте суффиксное дерево для заданной строки s.
Входные данные
Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100000). Строка состоит из строчных латинских букв.
Выходные данные
В первой строке выходного файла выведите два натуральных числа n и m, разделённых пробелом - число вершин и рёбер в суффиксном дереве соответственно. В следующих m строках выведите описания рёбер в формате <родитель> <потомок> <l> <r>. Эта запись означает, что на ребре написана строка s[l..r], при этом значение l должно быть минимально возможным. Корнем дерева должна быть вершина с номером 1. Вершины должны быть занумерованы натуральными числами, не превышающими n,
Пример
Входные данные #1
ababb
Выходные данные #1
7 6 1 4 1 2 1 6 2 2 4 2 3 5 4 5 5 5 6 3 3 5 6 7 5 5