BZPRO
#2537. [neerc2007]Language Recognition
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
DFA（确定性有限状态自动机）是一个有向图，顶点称为状态，边称为转移。每个转移用一个字母标记。对于每个状态s和每个转移l，至多有一个转移从s出发且标记为l。DFA有一个初始状态和若干个结束状态。DFA定义的语言的单词可以由从开始状态到结束状态的路径上所有的字母连接起来。
图中表示一个语言（包括单词：fix,foo,ox）的DFA。第一个DFA有7个状态，它不是最优的。第二个DFA定义的是同一个语言，但只有5个状态。
给定一个语言，包含有限个单词，求出定义该语言的DFA得最少状态数。
输入格式
第一行有一个整数n(1<=n<=5000)，表示语言的单词数。接下来n行，每行一个单词。每个单词由1到30个小写字母组成。输入的所有单词互不相同。
输出格式
一个数，定义该语言的DFA得最少状态数。
样例
样例输入
3
fix
foo
ox
样例输出
5
数据范围与提示
BZPRO