eolymp
bolt
Try our new interface for solving problems
Məsələlər

Распознание языка

Распознание языка

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Детерминированный конечный автомат (ДКА) представляет собой ориентированный мультиграф, вершинами которого являются состояния, а ребра - переходами. Каждый переход ДКА помечен одной буквой. Более того, для каждого состояния s и каждой буквы l существует не более одного перехода, исходящего из s и помеченного как l. ДКА имеет одно стартовое состояние и множество финальных. ДКА определяет язык всех слов, которые могут быть построены в результате записи подряд букв на пути со стартового состояния в некоторое конечное.

Язык задан конечным множеством слов, всегда можно сконструировать ДКА, определяющий этот язык. Слева приведен ДКА распознающий язык из трех слов: fix, foo, ox. Однако этот ДКА имеет 7 состояний, что не оптимально. ДКА справа определяет язык имея всего 5 состояний.

prb7595.gif

Вам следует найти наименьшее количество состояний в ДКА, который определяет заданный язык.

Giriş verilənləri

Первая строка содержит число n (1n5 000) - количество слов в языке. Каждая из следующих n строк содержит одно слово. Каждое слово содержит от 1 до 30 латинских букв нижнего регистра от "a" до "z". Все слова разные.

Çıxış verilənləri

Вывести наименьшее количество состояний ДКА, определяющий заданный на входе язык.

Nümunə

Giriş verilənləri #1
3
fix
foo
ox
Çıxış verilənləri #1
5
Giriş verilənləri #2
4
a
ab
ac
ad
Çıxış verilənləri #2
3
Mənbə 2007 ACM NEERC, Semifinals, November 28, Problem L