[日常训练]自动机

Description

确定优先状态自动机$(DFA)$的节点被称为状态，边被称为转移，是一个有向图。每一个$DFA$的转移都被标记为一个字母。而且，对于每一个状态$s$和一个字母$l$，最多只有一个转移从状态$s$开始，并且被标记为$l$。$DFA$有一个开始状态，和若干个结束状态。由$DFA$定义的语言是指，所有可通过按顺序记录从开始状态出发直到任一结束状态的路径上的字母所构成的单词组成的集合。

现在给你一个语言，请你输出其对应的状态数最小的$DFA$的状态数。若不存在，则输出$-1$。

Input

第一行包含一个整数$n$，表示语言中的单词数。

接下来$n$行，每行包含一个单词。每个单词长度不超过$30$，且只包含小写字母。所有单词保证不相同。

Output

输出一个整数，如题目要求。

Sample Input

fix

foo

Sample Output

HINT

$1;leq;n;leq;5000$

Solution

显然，不存在无解的情况。

$trie$树是一个合法的但是比较劣的解。

合并后缀可以减少节点开支，用树哈希即可。

由于题目给的是图上所有从起点到终点的路径，所以要对结束节点打上标记，避免构图时节点数比标准答案少。

（人生第一道树哈希）

 1 #include<set> 
 2 #include<cmath>
 3 #include<ctime>
 4 #include<queue>
 5 #include<stack>
 6 #include<cstdio>
 7 #include<vector>
 8 #include<cstring>
 9 #include<cstdlib>
10 #include<iostream>
11 #include<algorithm>
12 #define K 27
13 #define M 31
14 #define N 5001
15 #define T 150001
16 #define U 233329
17 #define V 666649
18 #define W 1000000007
19 using namespace std;
20 typedef long long ll;
21 struct trie{
22     int chd[K],key;
23 }t[T];
24 int l,n,cnt;char c[M];
25 ll f[K<<1];set<ll> s;
26 inline void insert(int u,int k){
27     int m=c[k]-'a'+1;
28     if(k==l){
29         if(t[u].key<=26)
30             t[u].key+=26;
31         return;
32     }
33     if(t[u].chd[m])
34         insert(t[u].chd[m],k+1);
35     else{
36         t[++cnt].key=m;
37         t[u].chd[m]=cnt;
38         insert(t[u].chd[m],k+1);
39     }
40 }
41 inline void print(int u){
42     printf("%d:%d
",u,t[u].key);
43     for(int i=1;i<K;i++)
44         if(t[u].chd[i]){
45             printf("t[%d].chd[%d]=%d
",u,i,t[u].chd[i]);
46             print(t[u].chd[i]);
47         }
48 }
49 inline ll hash(int u){
50     ll ret=0;
51     for(int i=1;i<K;i++)
52         if(t[u].chd[i])
53             ret=(ret^(hash(t[u].chd[i])*U%W))%W;
54     if(t[u].key>26) s.insert(ret^K);
55     else s.insert(ret);
56     ret=(ret+t[u].key*V%W*f[t[u].key]%W)%W;
57     return ret;
58 }
59 inline void init(){
60     scanf("%d",&n);
61     for(int i=1;i<=n;i++){
62         scanf("%s",&c);
63         l=strlen(c);
64         insert(0,0);
65     }
66     srand(time(0));
67     for(int i=(K<<1)-1;i;i--)
68         f[i]=rand()%U+1;
69     hash(0);
70     printf("%d
",s.size());
71 }
72 int main(){
73     freopen("dfa.in","r",stdin);
74     freopen("dfa.out","w",stdout);
75     init();
76     fclose(stdin);
77     fclose(stdout);
78     return 0;
79 }