主要是对树的hash，其实这题比3274 Gold Balanced Lineup还要容易，且时限放得更宽，建议对hash比较感兴趣的同学做此题，当然对于用map者，就更简单了。

题目要求一个dfa，它满足两个条件，1、能识别所有词的dfa，2、要求状态数最少。

其实，trie也可以看做是满足第一个条件的dfa，但是它不满足第二个条件

这里设trans[i][x]表示状态i读取字符x所对应的转移。
我们设状态a有一颗子树为 t1(trans[a][i] = t1)，b的一颗子树t2 (trans[b][j] = t2)，如果t1和t2是一样的树，那么我们可以让 trans[a][i] = trans[b][j] = t1; 这样就节省了一颗子树的状态数。

所以，我们可以在dfs的过程中对树进行hash和判重，不过完美hash不太可能做到。

下面说说我的hash方案，设hashVaulue[i]表示状态i所代表的树的hash值，hash[x] 表示hash值x所对应的树，size为hash表大小。

对于状态cur， p = sigma( hashValue[trans[cur][i]] * 26 + i) mod size (i=1..26, 且trans[cur][i]有对应转移。）
那么hashValue[cur] 就等于对 p进行线性探测所确定得值。

这样hash方案是基于rabin-karp的，如果trie退化成一条链，就是非常明显的rabin-karp了。

• Re:200题纪念，写个思路 (24) crackerwang 2008-07-30 15:04:20
• hash_map过了 不过为什么这个题也spj.... (701) 20053565 2008-12-08 21:47:42
• 大牛的办法真快....赞~ (701) AngelClover 2009-01-20 15:01:06