Pseudo automaton
Pseudo automaton
Дана строка S. Построить детерминированный конечный автомат, принимающий все суффиксы строки S (и возможно другие конечные строки). Автомат должен состоять из минимального числа состояний. Каждое состояние автомата объявляется финальным. Начальное состояние имеет номер 1.
На изображении ниже показан автомат из тестового примера для строки "abacaba".
Входные данные
В единственной строке слово S, состоящее из строчных латинских букв.
Выходные данные
В первой строке два числа N и K — количество состояний и количество переходов. Далее K строк, в каждой из которых по два числа a_i, b_i и буква c_i, означающие наличие перехода из состояния a_i в b_i по букве c_i. Переходы можно выводить в любом порядке. Если решений несколько, можете вывести любое из них.
Ограничения
1 ≤ |S| ≤ 5000
1 ≤ a_i, b_i ≤ N
'a' ≤ c_i ≤ 'z'
Пример
abacaba
8 10 1 2 a 1 3 b 1 5 c 2 3 b 2 5 c 3 4 a 4 5 c 5 6 a 6 7 b 7 8 a