Напишите программу, моделирующую работу детерминированного конечного автомата (ДКА). Описание автомата и входная строка вводятся на стандартном потоке ввода. Результат работы автомата над данной строкой выводится на стандартный поток вывода.
Входные данные
Описание автомата задаётся в следующей форме. Сначала задаётся функция перехода автомата. Функция перехода задаётся в виде троек CUR CHAR NEW, где CUR — идентификатор исходного состояния — произвольная символьная строка, не содержащая пробельные символы. CHAR — символьная строка длиной ровно 1 символ. NEW — идентификатор целевого состояния — произвольная символьная строка, не содержащая пробельные символы. Элементы описания перехода могут отделятся друг от друга произвольным количеством пробельных символов. Описание функции перехода завершается строкой "END" в качестве идентификатора исходного состояния. Элементы CHAR и NEW отсутсвуют.
Далее перечисляются заключительные состояния автомата. Каждое состояние — это символьная строка. Список состояний завершается символьной строкой "END". Далее задаётся начальное состояние автомата — символьная строка. Затем задаётся проверяемое слово — символьная строка. Все элементы входного файла могут отделяться друг от друга произвольным количеством пробельных символов. Можете предполагать, что входные данные корректны, то есть удовлетворяют спецификации и действительно задают детерминированный конечный автомат.
Выходные данные
Результат работы автомата должен быть напечатан в следующем виде. Сначала напечатайте число 1, если данный автомат допускает данную цепочку, и 0 в противном случае. Затем напечатайте количество символов, прочитанных во входной цепочке к моменту принятия автоматом решения. Наконец, напечатайте идентификатор состояния, в котором в данный момент находился автомат.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
S a S
END
S END
S
aaaa
|
1
4
S
|
|
2
|
S a S
END
S END
S
aaaba
|
0
3
S
|